점화식과 Master 방법론

점화식을 구하는 방법에는 총 3가지가 존재한다.

• 재귀 트리 (Recursion Tree)
• 치환법 (Substitution method)
• 마스터 방법 (The Master method)

이 중 치환법의 경우 제한적으로만 사용 가능하기에(추측을 통한 방법이다.) 일반적으로 재귀 트리, 마스터 방법을 주로 사용한다.

 

1. 점화식이란?

수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식.

 

2. 마스터 방법이란?

시간 복잡도를 계산하는 $Big - O$(worst) 표기법을 보면

$$ O(1), O(n), O(n\,log\,n), O(n^{3}), etc... $$

이러한 대표적인 Big-O 표기법으로 표현될 수 있는 대다수의 식들은 간편하게 구할 수 있지만(반복문이 중첩으로 몇개인가 등.) 그렇지 않은 몇몇 식들을 계산하기 위해서 존재하는 것이 위 3가지 방법론으로, 대부분 분할정복 알고리즘의 시간 복잡도를 구하기 위해서 사용되며, 마스터 방법 또한 그 중 하나이다.

 

3. 마스터 방법 계산법

마스터 방법을 사용하기 위한 일반적인 점화식의 형태는 아래와 같다.

$$ T(n) = a \times T({n \over b}) + f(n) $$

각 기호가 나타내는 정보는 아래와 같다.

• $a \geq 1$ : 하위 문제의 수
• $b > 1$ : 분할의 비율
• $f(n)$ : 하위 문제 외 수행되는 작업의 복잡도

위 점화식은 $a$와 $b$가 양의 상수일 때 문제 크기 $n$을 각각 ${n\over b}$ 인 $a$개의 하위문제로 나누는 수행시간을 나타낸다. 여기서 이 $a$개의 하위 문제는 각각 $T({a \over b})$시간에 재귀적으로 풀린다. 문제를 나누고 하위 문제들의 결과를 합치는 데 드는 비용은 함수 $f(n)$으로 나타낸다.

이러한 마스터 방법론의 핵심은 결국 $n^{log_b a}$ 와 $f(n)$ 두개를 서로 비교하는 것으로, 아래와 같은 3개의 Case 로 정리된다.

※ $\epsilon$ 은 $f(n)$의 증가속도와 $n^{log_b a}$의 증가 속도 사이의 상대적 차이를 나타내는 상수이다.

Case 1 : $f(n) = O(n^{log_b a - \epsilon})$ ($\epsilon$>0)

$f(n) < n^{log_b a}$ 일 때 사용한다.

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

 

Case 2 : $f(n) = \Theta(n^{log_{b} a})$

$f(n) = n^{log_b a}$ 일 때 사용한다.

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

 

Case 2 : $f(n) = \Theta(n^{log_b a} log^{k} n) (k \geq 0)$

$f(n) = n^{log_b a}$ 이며, $f(n) $ 이 로그를 포함할 때 사용한다.

$$ T(n) = \Theta(n^{log_{b}a}log^{k+1}n) $$

 

Case 3 : $f(n) = \Omega(n^{ \log_b a + \epsilon })$ ($\epsilon$ > 0) 이며, $af({n \over b}) \le cf(n)$ ($c$<1) 을 만족시킬때 사용

$f(n) > n^{log_b a}$ 일 때 사용한다.

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

 

4. 문제 풀이.

위에서 설명한 내용을 기반으로 문제를 풀어본다.

 

1) $T(n) = 5T({n \over 2}) + \Theta(n^2)$

위에서 언급했듯  $n^{log_b a}, n^2$ 를 서로 비교하면 된다.

→ $n^{log_2 5} , n^2$
→ $n^2 < n^{2.32 - \epsilon}$ 으로 $f(n)$ 이 더 작으므로 Case 1 이 적용된다.
→ $T(n) = \Theta(n^{log_2 5})$

 

2) $T(n) = 27T({n \over 3}) + \Theta(n^3 log n)$

마찬가지로  $n^{log_b a}, n^3$ 을 비교하면 된다.

→ $n^{log_3 27} = n^3$ 으로 서로 값이 같다. 이는 Case 2 가 적용되며, $f(n)$ 에 로그 펙터가 포함됨.
→ $T(n) = \Theta(n^{log_3 27} log^{1+1} n)$
→ $ T(n) = \Theta(n^3 log^2n)$ 

 

3) $T(n) = 5T({n \over 2}) + \Theta(n^3)$

→ $n^{log_2 5} < n^3$ 으로 $f(n)$ 이 더 크므로, Case 3 가 적용된다.
→ Case 3 는 추가적으로  $af({n \over b}) \le cf(n)$ (c < 1) 조건을 만족해야 한다.
→ ${5n^3 \over 8} \le cn^3$
→ 즉 ${5 \over 8} < 1$ 이므로 부가 조건 역시 만족한다.
→ $T(n) = \Theta(n^3)$

 

4) $T(n) = 10T ({n \over 2}) + n^3$

→ $n^{log_2 10} > n^3$ 으로 $f(n)$ 이 더 작으므로 Case 1 이 적용된다.
→ Case A의 해를 구하는 방식은 $T(n) = \Theta(n^{log_{b}\, a})$ 이다.
→ $T(n) = \Theta(n^{log_2 10})$​