[알고리즘] 시간복잡도와 공간복잡도

[yeoseon]

알고리즘을 풀면서, 시간복잡도와 공간복잡도를 고려할 수 있을만큼 공부하고 Close할 것

빅오표기법

시간복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 분석을 좀 더 간편하게 할 목적으로 만들어진 함수

아래 시간복잡도 예시의 Case 2를 보자

sum <- 0
/* 이 부분 */
for i <- 1 to n do
    sum <- sum + n;

// i <- 1 : 대입 연산 1회
// to : n + 1 번의 비교 연산(루프를 탈출하기 직전의 비교 연산 포함)
// n : n 번의 연산

• 하나의 루프 제어문은 2n+2개의 연산을 추가하게 된다.
• 결과적으로 2n+1 + 2n+2의 연산이므로 4n+3이 된다.
• 구체적인 연산 횟수보다, 증가 추세가 중요하다.
• N이 커진다면 4n+3이든 2n+2이든 별 차이가 없는 수가 된다.
• 가장 중요한 포인트는 n에 비례한다는 것이다.
• 이는 O(n)으로 표기하고, '빅오엔', '빅오of엔'이라고 읽는다.

빅오표기법의 수학적 정의와 예시

f(n), g(n)이 주어졌을 때, 모든 n >= n0 에 대하여 |f(n)| <= c|g(n)|을 만족하는 2개의 상수 c와 n0이 존재하면 f(n) = O(g(n))이다.

예시

1. f(n) = 5 이면 O(n) 이다. n0 = 1, c = 10 일 때, n>=1에 대하며 5<=10*1이 되기 때문이다.
2. f(n) = 2n + 1이면 O(n) 이다. n0 = 2, c = 3일 때, n>=2에 대하면 2n + 1 <= 3n이 되기 때문이다.
3. f(n) = 3n^2 + 100이면 O(n^2)이다. n0 = 100, c =5일 때, n >= 100에 대하며 3n^2 + 100 <= 5n^2이기 때문이다.

많이 쓰이는 빅오표기법

(출처: https://madplay.github.io/post/time-complexity-space-complexity)

시간복잡도와 시간복잡도 함수

알고리즘의 절대적인 시간 X
알고리즘을 수행할 때의 연산(산술, 대입, 비교, 이동 등)이 몇 번 이루어지는 지를 숫자로 표기한다.
연산의 실행 횟수는 입력한 데이터의 개수를 나타내는 n에 따라 정해진다.
입력한 데이터 개수를 통한 함수로 나타낸 것을 '시간복잡도 함수'라고 하며, T(n)으로 표현한다.

시간 복잡도 계산 예시

/* Case 1 */
sum <- n * n;

/* Case 2 */
sum <- 0
for i <- 1 to n do
    sum <- sum + n;

/* Case 3 */
sum <- 0
for i <- 1 to n do
    for j <- 1 to n do
        sum <- sum + 1;

잘 이해가 가지 않았다.
Case1의 대입 횟수가 2인 이유는 대입 연산 1 + 곱셈연산 1 이기 때문인 것 같다. (표에 누락되었나?)
Case2에는 곱셈 연산이 없다. 표에 있는 곱셈 연산을 제외해야지 2t+1로 맞게 나오는 것 같다.
Case3에는 +1은 0을 먼저 대입하는 연산인 것 같다.

최선, 평균, 최악의 경우

동일한 알고리즘의 경우에도 입력되는 데이터에 따라 다른 실행 시간을 보일 수 있다.
따라서 3가지로 나누어 평가한다.

1. 최선의 경우 : 실행 시간이 가장 적은 경우
2. 평균적인 경우 : 모든 입력을 고려하고, 각 입력이 발생하는 확률을 고려한 평균 수행 시간
3. 최악의 경우 : 알고리즘의 수행 시간이 가장 오래 걸리는 경우

주로 최악의 경우를 사용한다.

예시

• 정렬되지 않은 배열을 순차 탐색하여 특정한 값을 찾는 경우의 예시

  int sequencialSearch(int list[], int n, int key)
  {
  int i;
  for(i = 0; i < n; i++)
  {
      if(list[i] == key)
      {
          return i; // 탐색에 성공하면 키 값의 인덱스 반환
      }
  }
  return -1; // 탐색에 실패하면 -1 반환
  }

• 최선의 경우 : 찾으려는 값이 배열의 가장 처음에 있는 경우 -> O(1)
• 최악의 경우 : 가장 마지막에 있는 경우 -> O(n)

공간 복잡도

프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
S(P) = c + Sp(n)

• 고정 공간 : 입력과 출력의 횟수나 크기와 관계없는 공간의 요구
  • 코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수 등
• 가변 공간 : 동적으로 필요한 공간
  • 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간
  • 함수가 순환 호출을 할 경우 요구되는 추가 공간

공간 복잡도 계산 예시

• 예제 1

  int factorial(int n)
  {
  if(n > 1) return n * factorial(n - 1);
  else return 1;
  }

• n이 1 이하일 때까지 함수가 재귀적으로 호출된다.

• 스택에는 n부터 1까지 모두 쌓이게 된다.

• 즉 공간 복잡도는 O(n)이다.

• 예제 2

  int factorial(int n)
  {
  int i = 0;
  int fac = 1;
  for(i = 1; i <= n; i++)
  {
      fac = fac * i;
  }
  return fac;
  }

• n의 값과 관계 없이 스택에는 n과 i, 그리고 fac 변수만 저장된다.

• 즉 공간복잡도는 O(1)이다.

시간복잡도 vs 공간복잡도

시간복잡도는 '얼마나 빠르게 실행되느냐'
공간복잡도는 '얼마나 많은 자원이 필요한가'

좋은 알고리즘이란, 시간도 적게 걸리고 자원의 사용도 적어야 한다.

하지만 시간과 공간은 반비례적인 경향이 있기 때문에, 알고리즘의 척도는 주로 '시간복잡도'를 위주로 판단한다.

Reference

• 시간복잡도와 공간복잡도