Master Theorem

왜 마스터 정리인가?

병합 정렬의 시간 복잡도를 구한다고 하자. 입력을 절반으로 나눠 각각 정렬한 뒤 합치는 과정은 다음과 같은 점화식으로 표현된다.

$T(n) = 2T\!\left(\frac{n}{2}\right) + \Theta(n)$

이 식을 직접 풀려면 점화식을 $\log_2 n$ 단계까지 전개하고 각 단계의 비용을 합산해야 한다. 같은 과정을 이진 탐색($T(n) = T(n/2) + \Theta(1)$), Karatsuba 곱셈($T(n) = 3T(n/2) + \Theta(n)$), Strassen 행렬 곱($T(n) = 7T(n/2) + \Theta(n^2)$)에도 반복해야 한다. 분할 정복 알고리즘이 하나 등장할 때마다 같은 종류의 전개 작업을 처음부터 다시 해야 한다는 뜻이다.

마스터 정리는 이 반복 노동을 제거한다. $T(n) = aT(n/b) + f(n)$이라는 공통 틀에 점화식을 끼워 맞추고, $a$·$b$·$f(n)$만 보면 결론이 나온다. 분할 정복 알고리즘의 복잡도를 기계적으로 판정하는 치트 시트(cheat sheet)인 셈이다.

분할 정복과 점화식

마스터 정리가 다루는 점화식은 분할 정복 알고리즘의 구조를 그대로 반영한다.

$T(n) = \underbrace{a \cdot T\!\left(\frac{n}{b}\right)}_{\text{부분 문제 } a \text{개}} + \underbrace{f(n)}_{\text{분할·결합 비용}}$

각 항의 의미는 다음과 같다.

$a \geq 1$은 크기 $n$의 문제를 해결하기 위해 만들어 내는 부분 문제의 개수다. 병합 정렬은 2개, Strassen은 7개, 이진 탐색은 1개를 만든다. $b > 1$은 부분 문제의 축소 비율로, 원 문제의 크기가 $1/b$로 줄어든다는 의미다. $f(n)$은 부분 문제를 만들어 내고divide 부분 해를 합치는combine 데 드는 비용이다. 병합 정렬에서는 병합이 $\Theta(n)$, Karatsuba에서는 덧·뺄셈이 $\Theta(n)$, 이진 탐색에서는 중간 원소 비교가 $\Theta(1)$에 해당한다.

재귀 트리로 직관 얻기

점화식을 풀기 전에, 이를 재귀 트리로 시각화하면 세 가지 경우가 어디에서 비롯되는지가 한눈에 보인다. 단순화를 위해 $a = 2$, $b = 2$인 경우를 그려 보자. 이는 병합 정렬과 동일한 구조다.

레벨별 비용을 정리하면 다음과 같다.

깊이 $k$인 레벨에는 $a^k$개의 부분 문제가 존재하며, 각 부분 문제의 크기는 $n/b^k$이다. 따라서 그 레벨에서 발생하는 결합 비용의 합은 다음과 같다.

$W_k = a^k \cdot f\!\left(\frac{n}{b^k}\right)$

트리의 깊이는 $n/b^k = 1$이 되는 지점, 즉 $k = \log_b n$이다. 최하단 잎의 개수는 $a^{\log_b n} = n^{\log_b a}$이며, 각 잎에서는 $T(1) = \Theta(1)$의 상수 비용이 든다. 전체 수행 시간은 모든 레벨의 비용과 잎의 비용을 더한 값이다.

$T(n) = \underbrace{\sum_{k=0}^{\log_b n - 1} a^k f\!\left(\frac{n}{b^k}\right)}_{\text{내부 노드의 결합 비용}} + \underbrace{\Theta\!\left(n^{\log_b a}\right)}_{\text{잎의 상수 비용}}$

이 합을 지배하는 항이 무엇인가에 따라 세 가지 경우가 갈린다. $n^{\log_b a}$이라는 값이 결합 비용 $f(n)$과 대결하는 분수령watershed² 역할을 하며, 두 값 사이의 대소 관계가 정답을 결정한다.

마스터 정리의 진술

가장 널리 쓰이는 단순 형태는 $f(n) = \Theta(n^d)$, 즉 결합 비용이 다항식인 경우로 제한한다. 이 제약을 푼 일반 형태는 뒤에서 다루기로 하고, 실무에서 거의 모든 경우를 커버하는 이 단순 형태부터 살펴보자.

비교의 축은 $a$와 $b^d$이지만, 양변에 $\log_b$를 취하면 $\log_b a$와 $d$의 비교로 바뀐다. 이 동치 조건이 세 가지 경우를 "잎의 개수 $n^{\log_b a}$"와 "뿌리의 비용 $n^d$" 사이의 대결로 읽게 해 준다.

잎이 지배 ($a > b^d$)

$a > b^d$는 부분 문제가 너무 많이 만들어져서, 잎의 수가 결합 비용을 압도한다는 뜻이다. 각 레벨의 비용 $W_k = a^k f(n/b^k) = a^k (n/b^k)^d = n^d (a/b^d)^k$는 $a/b^d > 1$에 의해 기하급수적으로 증가한다. 이런 등비수열의 합은 마지막 항에 지배되므로, 전체 비용은 잎 레벨의 비용 $\Theta(n^{\log_b a})$에 수렴한다.

Strassen 알고리즘과 Karatsuba 곱셈이 이 경우다. 더 작은 부분 문제를 많이 만드는 것이 곧 전체 비용을 키운다.

균형 ($a = b^d$)

$a = b^d$이면 $W_k = n^d (a/b^d)^k = n^d$가 모든 레벨에서 일정하다. 즉 각 레벨이 정확히 같은 비용 $n^d$를 부담하며, 레벨의 개수는 $\log_b n$이므로 총합은 $n^d \log_b n$이다. $\log_b n$과 $\log n$은 상수 배 차이이므로 $\Theta$ 표기 안에서는 같다.

병합 정렬과 이진 탐색이 대표적이다. 결합 비용과 부분 문제 개수가 "정확히 균형"을 이룰 때 $\log n$ 인자가 하나 붙는다.

뿌리가 지배 ($a < b^d$)

$a < b^d$인 경우 $W_k = n^d (a/b^d)^k$는 $a/b^d < 1$에 의해 기하급수적으로 감소한다. 이런 등비수열의 합은 첫 항에 지배되므로, 전체 비용은 뿌리 레벨의 $\Theta(n^d)$에 수렴한다. 잎의 수가 상대적으로 적어 결합 비용이 전체를 좌우한다.

실제 알고리즘에서는 드물게 나타나지만, 정렬된 데이터 위에서의 선형 스캔 후 이진 분할 같은 혼합 패턴에서 관찰된다.

실제 알고리즘에 적용하기

세 경우를 네 개의 고전 알고리즘에 대입해 보자.

병합 정렬

$T(n) = 2T\!\left(\frac{n}{2}\right) + \Theta(n)$

$a = 2$, $b = 2$, $d = 1$이다. $b^d = 2 = a$이므로 2번 케이스에 해당한다. 따라서

$T(n) = \Theta(n \log n)$

이다. 병합 정렬이 $\Theta(n \log n)$인 이유가 바로 이 균형 조건에 있다. 부분 문제의 개수 증가율과 결합 비용의 감소율이 정확히 상쇄된다.

이진 탐색

$T(n) = T\!\left(\frac{n}{2}\right) + \Theta(1)$

$a = 1$, $b = 2$, $d = 0$이다. $b^d = 1 = a$이므로 이 역시 2번 케이스다.

$T(n) = \Theta(\log n)$

결합 비용 $f(n) = \Theta(1) = \Theta(n^0)$이고 잎의 개수 $n^{\log_2 1} = n^0 = 1$로 둘이 같다. 레벨마다 상수 비용이 발생하고 레벨 수가 $\log_2 n$이므로 총합이 $\log n$이다.

Karatsuba 곱셈

Karatsuba 곱셈은 $n$자리 정수 두 개의 곱셈을 세 번의 $n/2$자리 곱셈과 $\Theta(n)$의 덧·뺄셈으로 해결한다.

$T(n) = 3T\!\left(\frac{n}{2}\right) + \Theta(n)$

$a = 3$, $b = 2$, $d = 1$이다. $b^d = 2 < 3 = a$이므로 1번 케이스에 해당한다.

$T(n) = \Theta\!\left(n^{\log_2 3}\right) \approx \Theta\!\left(n^{1.585}\right)$

초등학교 곱셈법의 $\Theta(n^2)$을 처음으로 깬 알고리즘이다. 부분 문제를 4개 대신 3개로 줄인 것이 $n^2$에서 $n^{1.585}$로의 감소를 만든다. 자세한 항등식과 구현은 별도 포스트에서 다룬다.

Strassen 행렬 곱

Strassen 행렬 곱은 $n \times n$ 행렬 곱을 8번의 $n/2$ 블록 곱 대신 7번으로 줄인다.

$T(n) = 7T\!\left(\frac{n}{2}\right) + \Theta(n^2)$

$a = 7$, $b = 2$, $d = 2$이다. $b^d = 4 < 7 = a$이므로 1번 케이스다.

$T(n) = \Theta\!\left(n^{\log_2 7}\right) \approx \Theta\!\left(n^{2.807}\right)$

표준 행렬 곱의 $\Theta(n^3)$ 벽을 처음 뚫은 결과다. 상수 인자가 커서 실용적으로는 충분히 큰 $n$에서만 이득이 있지만, "행렬 곱의 복잡도를 낮출 수 있다"는 가능성 자체가 이론적 사건이었다. 7개 곱셈 항등식의 구체적인 형태는 별도 포스트에서 다룬다.

네 예시의 공통점은 분명하다. $a$와 $b^d$의 대소만 비교하면, 재귀 전개를 한 번도 펼치지 않고 복잡도가 결정된다.

일반 형태

단순 형태는 $f(n) = \Theta(n^d)$라는 다항식 제약을 두지만, 실제 알고리즘의 결합 비용은 $n \log n$이나 $n^2 / \log n$처럼 순수 다항식이 아닐 수 있다. 이 제약을 푼 일반 형태는 다음과 같다.

"다항식 크기만큼 더 작다"(1), "같은 차수다"(2), "다항식 크기만큼 더 크다"(3)는 구별은 결국 $f(n)$과 분수령 $n^{\log_b a}$ 사이의 폴리노믹 갭을 따지는 것이다. 경우 3의 정규성 조건은 $f(n)$이 "재귀에 잘 협조적으로 줄어드는가"를 보장하며, $f(n)$이 다항식 꼴이면 자동으로 성립한다.

마스터 정리의 한계

마스터 정리는 만능이 아니다. 다음과 같은 경우에는 적용할 수 없다.

• 부분 문제가 서로 다른 크기로 쪼개질 때는 적용할 수 없다. 예를 들어 $T(n) = T(n/3) + T(2n/3) + \Theta(n)$처럼 불균등 분할이 일어나는 경우, $aT(n/b)$ 틀에 맞지 않는다. 이런 점화식은 Akra-Bazzi 정리⁴로 풀어야 한다.
• 다항식 크기의 차이가 없을 때도 적용할 수 없다. $T(n) = 2T(n/2) + n \log n$에서 $n^{\log_b a} = n$이고 $f(n) = n \log n$인데, $n \log n$은 $n$보다 커지지만 다항식 크기만큼 크지는 않다(모든 $\epsilon > 0$에 대해 $n \log n \neq \Omega(n^{1+\epsilon})$). 이 경우는 세 경우 어디에도 해당하지 않고, 결과는 $\Theta(n \log^2 n)$이다. 2번 케이스를 확장하거나⁵나 재귀 트리를 직접 분석해야 한다.
• 분할 비율이 상수가 아닐 때도 적용할 수 없다. $T(n) = T(\sqrt{n}) + \Theta(1)$($T(n) = \Theta(\log \log n)$)처럼 축소 비율 자체가 $n$의 함수인 점화식은 치환법으로 풀어야 한다.
• 점화식이 감소형이 아닐 때도 적용할 수 없다. $T(n) = T(n-1) + \Theta(n)$처럼 부분 문제가 선형적으로 줄어드는 퀵 정렬의 최악 경우는 마스터 정리의 대상이 아니다. 이런 점화식은 전개하면 $\Theta(n^2)$이 된다.

마스터 정리를 쓸 수 없는 경우가 생각보다 적지 않지만, 대부분의 교과서적 분할 정복 알고리즘은 이 정리로 충분히 커버된다.

---

출처

• Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press, Chapter 4.
• Bentley, J. L., Haken, D. and Saxe, J. B. (1980) 'A general method for solving divide-and-conquer recurrences', ACM SIGACT News, 12(3), pp. 36–44.
• Akra, M. and Bazzi, L. (1998) 'On the solution of linear recurrence equations', Computational Optimization and Applications, 10(2), pp. 195–210.
• Kleinberg, J. and Tardos, É. (2006) Algorithm Design. Boston: Pearson Addison-Wesley, Chapter 5.2.

Footnotes

1. 점화식recurrence relation은 수열의 항을 앞의 항들의 함수로 표현한 식이다. 알고리즘 분석에서는 $T(n)$을 더 작은 $T(\cdot)$의 함수로 표현해 재귀 호출의 비용 구조를 수식으로 포착한다. ↩

2. 분수령 함수watershed function $n^{\log_b a}$은 점화식 $T(n) = aT(n/b) + f(n)$의 재귀 트리에서 잎 개수의 점근적 크기에 해당한다. 결합 비용 $f(n)$이 이 값보다 다항식 크기만큼 작은지, 같은지, 큰지에 따라 전체 비용의 지배적 층이 결정되기에 "분수령"이라 불린다. ↩

3. 정규성 조건 $af(n/b) \leq c\,f(n)$ (어떤 $0 < c < 1$에 대해, 충분히 큰 $n$에서 성립)은 "부분 문제 $a$개의 결합 비용이 원 문제의 결합 비용보다 상수 배만큼 작다"는 요구다. 이 조건이 있어야 재귀 트리의 결합 비용이 뿌리에서 잎으로 내려갈수록 기하급수적으로 감소하여, 총합이 뿌리 비용 $f(n)$에 수렴한다. $f(n)$이 다항식이면 자동으로 성립한다. ↩

4. Akra-Bazzi 정리(1998)는 $T(n) = \sum_{i=1}^{k} a_i T(b_i n) + g(n)$ 꼴의 불균등 분할 점화식을 푼다. $\sum a_i b_i^p = 1$을 만족하는 $p$를 찾아 $T(n) = \Theta(n^p (1 + \int_1^n g(u)/u^{p+1} \, du))$로 해를 표현한다. 마스터 정리의 일반화에 해당한다. ↩

5. $f(n) = \Theta(n^{\log_b a} \log^k n)$ ($k \geq 0$) 형태의 점화식에 대한 2번 케이스의 확장은 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$을 보장한다. 순수 다항식이 아닌 로그 인자를 포함한 결합 비용을 커버하기 위해 도입된 보조 정리다. ↩