마스터 정리

어떠한 알고리즘의 시간 복잡도를 구하기 위해서는 (특히 분할 정복 알고리즘의 경우) 점화식을 풀게 될 때가 많다.

가령, 병합 정렬의 알고리즘 복잡도를 구하기 위해서는 다음과 같은 점화식을 풀어야 한다.

$$T(n) = \begin{cases}\Theta(1)\;(n=1)\\2T(n/2) + \Theta(n)\;(n>1) \end{cases}$$

재귀 트리를 작성한다면 직관적으로 복잡도가 $\Theta(n\log n)$임을 알 수 있지만, 마스터 정리를 이용하면 일반적인 경우의 풀이가 쉬워진다.

1. 마스터 정리

$T(n) = aT(n/b) + f(n)$형태의 점화식이 있을 때,

i) $f(n) = O(n^{\log_b a - \epsilon})$이면 $T(n) = \Theta(n^{\log_b a})$

ii) $f(n) = O(n^{\log_b a})$이면 $T(n) = \Theta(n^{\log_b a}\log n)$

iii) $f(n) = \Omega(n^{\log_b a + \epsilon})$이고 $af(n/b) \le cf(n)$인 상수 $c<1$이 존재하면 $T(n) = \Theta(f(n))$

먼저 $n^{\log_b a}$를 구한 뒤 그 상한, 하한을 따져보고 1~3번 케이스로 분류한다.

1, 2번 케이스일 경우 바로 대입하면 되고 3번 케이스인 경우 나머지 조건을 따져본다.

2. 예제

2-1.

$T(n) = 2T(n/4) + 1$

$n^{\log_4 2} = \sqrt{n}$이므로 1번 케이스.

$T(n) = \Theta(\sqrt{n})$

2-2.

$T(n) = 2T(n/4) + \sqrt{n}$

$n^{\log_4 2} = \sqrt{n}$이므로 2번 케이스.

$T(n) = \Theta(\sqrt{n} \log n)$

2-3.

$T(n) = 2T(n/4) + n^2$

$n^{\log_4 2} = \sqrt{n}$이므로 3번 케이스.

$2 (\frac{n}{4})^2 = \frac{n^2} {8}$이므로 상수 $c = \frac{1}{8}$이 존재

$T(n) = \Theta(n^2)$

3. 기타

마스터 정리로 풀지 못하는 점화식은 재귀 트리 혹은 직관적인 방법으로 풀어야한다.

예를 들어 $T(n) = T(n - 1) + \frac{1}{n}$

같은 경우 직관적으로 $T(n) = \log{n}$임을 알 수 있다.