<자료구조 알고리즘> 마스터 정리 Master theorem

 

점화식으로 표현되는 재귀알고리즘의 시간 복잡도를 계산하는 것은 간단한 일이 아니다. 
이 글에서는 재귀알고리즘의 시간 복잡도를 조금은 쉽게 계산할 수 있게 해 주는 Master theorem에 대해 알아보자
이름은 Master theorem 이지만 모든 점화식에 사용이 가능하지는 않고 $T(n) = aT(\frac{n}{b}) + f(n)$의 형태의 점화식에만 사용가능하다. 즉 재귀 트리에서 모든 leaf노드의 차수가 같을 때만 가능한 것이다. 

(a:  분할한 부분 문제의 수, b:  입력의 크기가 줄어드는 비율 당연히 $\geq 2$,  $T(\frac{n}{b})$ : 부분문제를 푸는데 걸리는 시간,  $f(n)$ :  merging에 필요한 시간)

 

Master theorem

$$T(n) = aT(\frac{n}{b}) + f(n)$$
 
$$T(n)\begin{cases}
 O(n^{\log_{b}{a}}) & \text{ if } f(n)=O(n^c), c < \log_{b}{a} \\
 O(n^{\log_{b}{a}}\log{n}) & \text{ if } f(n)=O(n^{c}), c = \log_{b}{a}  \\
 O(f(n)) & \text{ if } f(n)=O(n^c), c > \log_{b}{a}
\end{cases}$$
 
간단하게 이야기 하자면 병합에 걸리는 시간과 부분문제를 해결하는 시간 중에서 더 오래 걸리는 쪽의 영향을 더 많이 받아 시간복잡도가 정해진다는 것이다. 그러면 증명을 해 보도록 하자. 증명이 궁금하지  않다면 머리 아프니 건너 뛰어도 된다. 
 

반응형

증명

일단 $T(n)$을 시그마를 이용해서 정리해 보면 아래와 같아진다.
$$\begin{align*}
 T(n)&= f(n) + aT(\frac{n}{b})\\
 &= f(n) + af(\frac{n}{b}) + a^2T(\frac{n}{b^2})\\
 &= f(n) + af(\frac{n}{b}) + a^2f(\frac{n}{b^2})+ \cdots + a^{\log_{b}{n}}f(1)\\
 &= \sum_{i=0}^{\log_{b}{n}}a^if(\frac{n}{b^i})\\
\end{align*}$$
 
 
case1부터 보면 이때 $f(n) = O(n^c)$에서 $c<\log_{b}{a}$이다. 공비가 1보다 크기 때문에 고등학교 때 배웠던 등비수열의 합을 이용하여 시그마를 풀어보면 $\frac{(\frac{a}{b^c})^{\log_{b}{n}+1}-1}{\frac{a}{b^c}-1}$가 나오고 쓸데 없는 상수들을 지워보면 $O(n^{\log_{b}{a}})$가 나오게 되는 것을 알 수 있다.
$$\begin{align*}
 &O(\sum_{i=0}^{\log_{b}{n}}a^i(\frac{n}{b^i})^c)\\
 &= O(n^c\sum_{i=0}^{\log_{b}{n}}(\frac{a}{b^c})^i)\\
 &= O(n^c\frac{(\frac{a}{b^c})^{\log_{b}{n}+1}-1}{\frac{a}{b^c}-1})\quad (\because c < \log_{b}{a},b^c<a, \frac{a}{b^c} > 1)\\
 &= O(n^c\frac{a^{\log_{b}{bn}}}{bn^c})\\
 &= O(\frac{a^{\log_{b}{bn}}}{b})\\
 &= O(n^{\log_{b}{a}}) 
\end{align*}$$

case2는 $c=\log_{b}{a}$이기 때문에 $\frac{a}{b^c}$가 1인 경우이다 따라서 $\sum_{i=0}^{\log_{b}{n}}(\frac{a}{b^c})^i = \log_{b}{n}+1$ 따라서 $O(n^{\log_{b}{a}}\log{n})$가 되는 것을 볼 수 있다.
$$\begin{align*}
 &O(\sum_{i=0}^{\log_{b}{n}}a^i(\frac{n}{b^i})^c)\\
 &= O(n^c\sum_{i=0}^{\log_{b}{n}}(\frac{a}{b^c})^i)\\
 &= O(n^{\log_{b}{a}}\log{n}) \quad (\because c = \log_{b}{a},b^c=a, \frac{a}{b^c}= 1)
\end{align*}$$
 
마지막 case3는 $c>\log_{b}{a}$이다. 
$$\begin{align*}
 &O(\sum_{i=0}^{\log_{b}{n}}a^i(\frac{n}{b^i})^c)\\
 &= O(n^c\sum_{i=0}^{\log_{b}{n}}(\frac{a}{b^c})^i)\\
 &= O(n^c\frac{(\frac{a}{b^c})^{\log_{b}{n}+1}-1}{\frac{a}{b^c}-1})\quad (\because c > \log_{b}{a},b^c>a, \frac{a}{b^c} < 1)\\
 &= O(n^c)\quad \\
\end{align*}$$
(r은 상수)$\sum_{i=0}^{n}r^i = \frac{1-r^{n+1}}{1-r}$에서 $r < 1$일 때 n이 커짐에 따라 $r^n$이 작아지므로 합이 $\frac{1}{1-r}$이라는 상수에 수렴하게 된다.  따라서 $O(n^c\frac{(\frac{a}{b^c})^{\log_{b}{n}+1}-1}{\frac{a}{b^c}-1}) = O(n^2)$이다.
 
 

Exercises

merge sort 알고리즘의 시간 복잡도를 Master theorem을 사용하여 계산해 보자

 
위의 recursion tree에서 알 수 있듯이 재귀식 아래와 같다
$$T(n) = 2T(\frac{n}{2}) + O(n)$$
따라서 Master theorem 을 이용해 계산하면
$$a=2, b =2, c = 1$$
$$c = \log_{b}{a} =1$$
$$O(n\log{n})$$
우리가 아는 것처럼 $O(n\log{n})$이 나온다.
 

참고문헌
Introduction to Algorithms, third edition by Thomas H. Cormen, ‎Charles E. Leiserson, ‎Ronald L. Rivest · 2009 
MIT OpenCourseWare R1. Matrix Multiplication and the Master Theorem