Solving Recurrences-알고리즘02

 재귀함수의 식을 예로 다음을 볼 수 있다.

이러한 재귀식은 알고리즘을 분석할 때, 특히 recursive algorithm을 분석 할때 많이 쓰인다

예를 들면 n!을 구하는 알고리즘의 T(n)은 어떻게 구할까?

 

f(n)=n!

이라고 할때

f(n)=f(n-1)*n=f(n-2)*(n-1)*(n) .... 이다.

 

f(n)의 연산횟수를 T(n)이라고 한다면 

T(n)   

=   T(n-1) + 1   (f(n-1)과 n의 곱셈)   

=   T(n-2) + 1   (f(n-2)와f(n-1)의 곱셈)   +   1  이므로

 

따라서 f(n) = O(n) 이다.

그렇다면 이런식은 어떻게 풀까?

이런 복잡한 식들을 푸는 방법 3가지를 오늘 알아보자.

 

1. Substitution Method

귀납적 풀이랑 비슷하다.(이산수학에서나오는 것과 똑같은 거 같다)

이 풀이는 거의 3가지 과정으로 나뉜다.

수업시간에는 다음 3가지 과정으로 배웠다

1. Guess the form of the solution
2. Verify by induction
3. Solve for constants

먼저 T(n)이 O(g(n))이라고 가정을 한다. 즉 T(n) ≥ c·g(n) for all n≥n0 ifor certain c.

그리고 수학적 귀납법을 이용해 가정이 참임을 증명하고 BaseCase에 대해서 참임을 보여주면 된다. 예시로 한 문제를 풀어보자.

다음은 Binary Search 의 time complexity를 구하는 과정이다.

 

T(n) = d + T(n/2)

 

Guess: T(n) = O(logn)

 

Induction goal : T(n) ≤ c·logn for some c and n≥n0

Inductive hypothesis: T(n/2) ≤ c·log(n/2)

Proof of Induction goal:

T(n) = T(n/2) + d ≤ c·log(n/2) + d

= c·logn - c + d ≤ c·logn   (since -c + d  ≤ 0 when c ≥ d)       귀납법으로 증명완료

 

BaseCase: T(n) = θ(1) for all n<n0 

 

therefore T(n) = O(logn) .

 

하나 더 풀어보자

T(n) = 2T(√n) + logn

이런 문제는 m=logn 이라고 두고 치환을 한다.

풀이 : 

 

2. Recursive Tree(재귀트리)

사실 위의 substitution method는 직관적으로 수식을 보고 guess단계를 위해 추측을 해야 그 추측에 대한 증명을 할 수 있는데 보통 추측을 tight하게 하기가 쉽지않다. 이 recursive tree는 그런것에 활용이 된다.

 

재귀트리의 개념

다음 식을 재귀트리로 표현해보자.  트리의 각 level에서 소요되는 시간(여기서는 n^2)들을 모두 더하면 된다.

 

 

 

                                  T(n) --->

 

 

 

 

 

                                                 ---->

 

 

 

 

 

 

 

 

 

                                               --->

결국 각 level의 비용들은 등비수열의 형태를 나타내므로 쉽게 해답을 구할 수 있다.

3. Master Method

마스터 방법은 수행시간 식이 다음과 같은 형태를 띄거나 다음의 형태로 변환 가능한 경우에만 사용할 수 있다.

3가지 경우에 따라 그냥 공식을 때려 박으면 된다.

Case1:$f(n) = O(n^{ log_{b} a- \varepsilon } ) $  for   some   $\varepsilon > 0$ ,   then   $T(n) = \Theta (log_{b} a) $ 

 

 

 

Case2:$f(n) = \Theta (n^{ log_{b} a } )  $,   then   $T(n) = \Theta (log_{b} a) $ 

 

 

 

Case3:$f(n) = \Omega (n^{ log_{b} a+\varepsilon } ) $  for   some   $\varepsilon > 0$ ,   then   $T(n) = \Theta (log_{b} a) $ 
and if
$f(n/b) ≤ cf(n) $ for some c < 1 and all sufficiently large n, then  $T(n) = \Theta(f(n))$