[알고리즘] 시간복잡도와 Master Theorem

Master Theorem

$T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다

1. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$
2. $h_n = n^{log_b a}$
3. $f(n)$과 $h(n)$ 비교
   • if $f(n) < h(n)$, then $O(T(n)) = h(n)$
   • if $f(n) = h(n)$, then $O(T(n)) = h(n) \cdot \log n$
   • if $f(n) > h(n)$, then $O(T(n)) = f(n)$

제약 조건

1. $f(n)$은 asymptotically positive function (양의 함수) 이어야 한다.
2. $a \geq 1$ and $b > 1$이어야 한다.
3. the regularity condition that $a \cdot f(\frac{n}{b}) \leq c \cdot f(n)$ for some constant $c < 1$
   • $f(n)$이 지수함수, $\cos$ 함수, $\sin$ 함수 등이 되어서는 안 됨
4. $T(n) = aT(\frac{n}{b}) + n^k \log ^p (n)$의 형태일 때는 Adavanced Master Theorem을 적용해야 함

Adavanced Master Theorem

where $a \geq 1$, $k \geq 1$ is a real number

• (1) if $a > b^{k}$

$$T(n) = \Theta ( n^{ \log_{k} a })$$

• (2) if $a = b^{k}$

$$T(n) = \begin{cases} \Theta ( n^{ \log_{k} a } \log^{p+1}(n)) & p>-1 \newline \Theta ( n^{ \log_{k} a } \log\log n) & p=-1 \newline \Theta ( n^{ \log_{k} a }) & p<-1 \end{cases}$$

• (3) if $a < b^{k}$

$$T(n) = \begin{cases} \Theta ( n^{k} \log^{p}(n)) & p \geq 0 \newline \Theta ( n^{k}) & p<0 \end{cases}$$

 

---

연습문제 풀어보기

[알고리즘] 시간복잡도와 Master Theorem - 연습문제