[알고리즘] 마스터 정리, 보조 마스터 정리 (Master Theorem)

마스터 정리 (Master Theorem)

 

재현식으로 표현된 알고리즘의 동작시간을 점근적으로 계산해 간단하게 계산하는 방법

 

$T(n) = a T( \frac{n}{b} ) + f(n) $이고  $ a>b>1, n$이 음수가 아닌 정수일 때,

 

$$\begin{cases}T(n) \in \Theta (n^{\log _b a}) & \mathrm{if}\,\, f(n) \in O(n^{\log_b a- \epsilon }) \\ T(n) \in \Theta(n^{\log_b a} \log n) & \mathrm{if} \,\, f(n) \in O(n^{\lg _b a}) \\  T(n) \in \Theta(f(n)) & \mathrm{if} \;f(n) \in \Omega(n^{\log_b {a+\epsilon}}) , \,af(\frac{n}{b}) \leq cf(n)\; (c<1 )\end{cases} $$

 

 

보조 마스터 정리 (Auxiliary Master Theorem)

 

Master Theorem에서 세번째 조건 $c<1$ 만족하지 않는다면, 이 방법을 이용하자.

 

$k \geq 0$을 만족하고 $f(n) = \Theta(n^{\log_b^a} \lg^k n)$를 만족한다면,

 

$$T(n) = \Theta(n^{\log_b^a} \lg^{k+1} n) $$