시간 복잡도 관련 정리

주요 시간 복잡도

많이 쓰이는 시간 복잡도에 대한 비교이다. x축 기준으로 대략 1000까지의 범위에서 그린 그래프이다.

시간 복잡도와 실제 수행 시간

위에서 이야기하는 O(n) / O(log n) 따위의 이야기는 많이 들었지만, 그래서 실제로 어떻게 쓰는지에 대한 이야기는 많이 부딪혀보지 않으면 느끼기 어렵다. 내가 느낀대로 정리해본다. 당연히 절대적인 것은 아니다.

컴퓨터의 초당 연산 처리 능력

사람마다 말이 많은데, 대충 일반적인 사용자 PC 기준 초당 1억 ~ 10억 개의 연산 정도를 처리 가능하단 것이 중론이다. 물론 이것을 너무 믿으면 안되는게, 기본적으로 연산은 사람이 쓴 line 단위가 아니라 어셈블리 레벨의 instruction레벨로 봐야하기 때문이다 또한, 이 instruction을 어셈블리로 코드를 변환해서 정확히 몇개가 수행되는지 안다고 해도, 각 instruction마다의 수행시간이 동일하지 않으며, CPU가 prefetching도 하고, branch prediction도 하고, pipelining도 하기 때문에, 모든 요소를 알기란 어렵다. 정확한 수행시간이란 무조건 부딪혀봐야 아는 것(또한 시행시 항상 같지 않다)이다. 하지만 일반적으로는 보수적으로 1억을 기준점으로 잡아 풀고, 만약 이를 크게 넘어가지는 않을 것으로(즉, 10억 회 연산 정도라면) 예상된다면 상수최적화를 시도해보는 것이 좋을 것이다.

N 값 기준 허용되는 시간 복잡도

나는 N의 값에 따라 대략 아래와 같은 기준을 쓰고 있다.

• N <= 100: O(N^3), 최적화된 O(N^4) 알고리즘을 돌릴 수 있다.
• N <= 1,000: O(N^2), 주로 DP로 푸는 문제에서 많이 사용되는 범위이다.
• N <= 10,000: 여기부턴 대략 O(N^2)도 timeout 나기 쉽다. O(n log n) 정도가 허용된다고 봐야한다.
• N <= 100,000: 십만 단위를 넘어가면 슬슬 빡세다. O(N^2)는 무조건 timeout 나기 시작하는 구간. O(n log n) 와 동등, 혹은 그 이상의 알고리즘을 사용해야 한다.
• N <= 1,000,000: 여기부터는 O(n)을 슬슬 써야하는 단위이다. O(n log n)도 슬슬 시간이 소요되는 것이 눈에 들어오기 시작한다.
  • 추가적으로 알아야 것 중 하나는 루트로 줄이는 O(n^1/2), O(n * n^1/2) 기법도 자주 등장하는 시점이라는 것이다. 꼭 알아두자.
    • 가령 소수를 판정할 때 루트n까지 봐도 된다던지 등..
• N >= 1,000,000,000: O(log n)이 강제된다. O(n^1/2)도 잘 짜면 된다.

Master Theorem

마스터 정리 라고도 불리는 이 이론은 다음 수식을 의미한다. 재귀 관계식으로 표현한 알고리즘의 시간 복잡도를 계산하는데에 쓰인다.

엄밀히는 $a(\geq1)$와 $b(>1)$는 상수고, $f(n)$은 점근적으로 양인 함수라고 한다. $n$은 문제 크기이다. 분할 정복으로 문제크기 $n$인 문제가 $n/b$인 $a$개의 하위 문제로 나뉘어진다고 하면, $a$개의 하위 문제는 각각 $T(n/b)$ 시간에 풀 수 있을 것이다. 이 때, 문제를 나누고 각각의 결과를 합치는데 드는 비용이 $f(n)$이 되는 것이다.

이 때, $f(n)$에 따라 아래처럼 시간 복잡도가 계산된다.

1. $f(n) > n^{log_ba}$: $O(f(n))$
2. $f(n) \simeq n^{log_ba}$: $O(f(n)\log n)$
3. $f(n) < n^{log_ba}$: $O(n^{log_ba})$

Binary Search의 시간 복잡도 생각해보기

위 이론에 따르면, Binary Search의 시간 복잡도를 계산해볼 수 있다. 아래처럼 재귀로 구현한다고 생각해보자.

int bs(int s, int e, int t) {
    int m = (s+e)>>1;
    if (arr[m] == t) return m;
    if (arr[m] > t) return bs(s,m-1);
    else return bs(m+1,e);
}

이 경우, 함수에 진입하면 1개의 함수로 쪼개진다. 즉, $a=1, b=1$인 경우이다. 이 경우 $n^{log_ba} = n^0 = 1$이고, $f(n) = 1$이므로, 두번째 case에 해당한다. 시간 복잡도는 $O(f(n)\log n) = O(\log n)$이 된다.

Merge sort의 시간 복잡도 생각해보기

이 경우에도 마찬가지로 재귀로 구현된다고 생각해보자. 대략적인 함수는 아래처럼 된다.

// [s, e]
void mergeSort(int s, int e) {
   if (s >= e) return;
   int m = (s+e)>>1;
   mergeSort(s, m); mergeSort(m+1, e);
   // 이하 생략은 합치는 과정... 전체 원소에 대해서 f(n) = O(n)이 걸린다.
}

이 경우, 함수에 진입하면 2개의 함수로 쪼개진다. 또한, 구간도 $n/2$로 줄어든다. 즉, $a=2, b=2$인 경우이다. 이 경우, $n^{log_ba} = n^1 = n$이고, $f(n) = n$이다. 즉, 두번째 case이다. 시간 복잡도는 $O(f(n)\log n) = O(n \log n)$이 되겠다.