03 점화식과 알고리즘 복잡도 분석

점화식의 분석 방법

1. 반복대치

더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법

 

2. 추정 후 증명

결론을 추정하고 수학적 귀납법을 이용하여 증명하는 방법

$T(n) \le 2T(n/2) + n$

추정 : $T(n)=O(nlogn)$, 즉 충분히 큰 $n$에 대하여 $T(n) \le cnlogn$인 양의 상수 $c$가 존재한다.

induction base : $T(n) \le c \cdot 2log2$를 만족하는 $c$가 존재한다.

induction hypothesis와 전개 :

$n/2$에 대해 $T(n/2) \le c \cdot (n/2) \cdot log(n/2)$을 만족한다 가정하면,

$$\begin{align}T(n) &\leq 2T(n/2) + n \\ &\leq 2c(n/2)log(n/2) + n\\ &= 2c(n/2)log(n/2)+n\\ &= cnlogn - cnlog2 + n\\ &=cnlogn +(-clog2 +1)n\\ &\leq cnlogn\end{align}$$

이를 만족하는 상수 $c$가 존재한다. 이 상수 $c$와 $T(2)$를 위해 잡은 $c$ 중 큰 것을 잡으면 된다.

따라서 $T(n)=O(nlogn)$이다.

 

3. 마스터 정리

특정한 모양을 가진 점화식을 가지는 알고리즘의 시간복잡도를 바로 계산해낼수 있는 방법

$T(n)=aT(n/b)+f(n)$에서,

$n^{log_b a}=h(n)$이라 하자.

1. 어떤 양의 상수 $\epsilon$에 대하여 $\frac{f(n)}{h(n)} = O(1/n^{\epsilon})$이면, $T(n)=\Theta(h(n))$이다.

2. 어떤 양의 상수 $\epsilon$에 대하여 $\frac{f(n)}{h(n)} = \Omega(n^{\epsilon})$이고, 어떤 상수 $c(<1)$와 충분히 큰 모든 $n$에 대해 $af(n/b) \le cf(n)$이면 $T(n)=\Theta(f(n))$이다.

3. $\frac{f(n)}{h(n)}=\Theta(1)$이면 $T(n)=\Theta(h(n)logn)$이다.

 

마스터 정리의 informal 의미

1. h(n)이 더 무거우면 h(n)이 수행시간을 결정한다.

2. f(n)이 더 무거우면 f(n)이 수행시간을 결정한다.

3. h(n)과 f(n)이 같은 무게이면 h(n)에 $logn$을 곱한 것이 수행시간이 된다.