이 글에서는 크기 $n$인 문제를 $b$분의 1 크기의 문제 $a$개로 나누고 $\Theta(n^c)$에 「병합」하는 넓은 범주의 「분할 정복」 알고리즘의 점근적 복잡도에 관한 중요한 정리를 증명합니다.
마스터 정리. 다음과 같은 점화식이 있다고 합시다:
$$ T(n) = \begin{cases} a T(\frac{n}{b}) + \Theta(n^c), & n > n_0 \\ \Theta(1), & n \leq n_0 \end{cases} $$그러면 다음이 성립합니다.
- A. $c > \log_b a$이면 $T(n) = \Theta(n^c)$입니다.
- B. $c = \log_b a$이면 $T(n) = \Theta(n^c \log n)$입니다.
- C. $c < \log_b a$이면 $T(n) = \Theta(n^{\log_b a})$입니다.
증명. 이 점화식의 «재귀 트리»를 살펴봅시다. 이 트리에는 $\log_b n$개의 레벨이 있습니다. $k$번째 레벨에는 $a^k$개의 정점이 있으며, 각 정점의 비용은 $\left(\frac{n}{b^k}\right)^c$번의 연산입니다. 모든 레벨의 모든 정점에 있는 값을 합산해 봅시다:
$$ T(n) = \sum_{k=0}^{\log_b n} a^k \left(\frac{n}{b^k}\right)^c = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k $$A. $c > \log_b a$이면 $\sum (\frac{a}{b^с})^k$는 감소하는 등비수열의 합으로, $n$에 의존하지 않으며 단순히 어떤 상수와 같습니다. 따라서 $T(n) = \Theta(n^c)$입니다.
B. $c = \log_b a$이면
$$ T(n) = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k = n^c \sum_{k=0}^{\log_b n} 1^k = \Theta(n^c \log_b n) $$ C. $c < \log_b a$이면, 수열의 합은 점근적으로 그 가장 큰 항과 동치이므로, $$ T(n) = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k = \Theta\left(n^c \left(\frac{a}{b^c}\right)^{\log_b n}\right) = \Theta\left(n^c \cdot \frac{a^{\log_b n}}{n^c}\right) = \Theta(a^{\log_b n}) = \Theta(n^{\log_b a}) $$ 참고. 더 정밀한 “병합” 점근 복잡도 추정에 대해서는 이 정리가 아무것도 알려 주지 않습니다. 예를 들어, 병합에 $\Theta(n \log n)$이 걸리고 문제가 매번 두 부분으로 나뉜다면, 점근 복잡도는 다음과 같습니다: $$ \sum_{k=0}^{\log n} n \log \frac{n}{2^k} = \sum_{k=0}^{\log n} n (\log n - k) = n \sum_{k=0}^{\log n} k = \Theta (n \log^2 n) $$ 그런데 이 점화식은 정리의 조건에 해당하지 않습니다. $c = 1$과 $c = 1 + \varepsilon$을 각각 대입하여 부정확한 경계 $\Omega (n \log n)$과 $O(n^{1+\varepsilon})$을 얻을 수 있을 뿐입니다. $\varepsilon$이 아무리 작더라도 $n \log n$과 $n \log^2 n$은 점근적으로 $n^{1+\varepsilon}$보다 작다는 점에 유의하십시오.