[알고리즘] 점화식의 이해(recurrence relation)

점화식

• 수열의 귀납적 정의와 유사
• 차이 : 인접한 항간의 관계만을 다루는 것은 아니다.
• 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것. (수열 = 정의역이 정수인 함수)
• 되부름, 혹은 유사한 방식으로 문제를 풀 때 걸리는 시간을 구하는데에 사용함
  • ex) T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1
  • An = T(n), An = 2A(n-1) + 1

 

 

점화식을 푸는 법

 

1. 반복 대치 : 주어진 조건을 이용하여 점점 작은 함수로 반복해서 대치하는 방법. 침착하게 꼼꼼히!

2. 추정 후 증명 : 점화식의 결론을 추정하고, 귀납법으로 증명함. 반복 대치가 복잡할 때 유용함. but 추정이 쉽지 않을 수 있음

3. 마스터 정리 : 점화식 공식. 여기에서는 다루지 않는다.

 

 

반복 대치

 

예시 1

T(n) = T(n-1) + n, T(1) = 1 일때,

T(n) = T(n-1) + n = T(n-2) + n-1 + n = T(n-3) + n-2 + n-1 + n

  = … = T(1) + 2 + 3 + … + n

= n(n+1)/2 = Θ(n^2)

 

 

예시 2

T(n) = 2T(n/2) + n, T(1) = 1 일때,

→ n = 2^k (k = log2 n) 이라고 가정.

 

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

= 2{ 2T(n/4) + n/2 } + n

= … = 2^kT(n/2^k) + kn

 

→ 여기서 T(1)을 만들기 위해 k=log n (밑=2) 대입하면 nT(1) + nlog n = n*log n + n

( n log n <= n log n + n <= 2n log n )

= Θ(n log n)

 

 

추정 후 증명

 

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

 

추정 : T(n) = O(n log n), 즉 T(n) ≤ cn log n 이라고 추정한다.

2T(n/2) + n ≤ cn log n

 

증명 :

T(n) = 2T(n/2) + n ≤ 2c(n/2)log(n/2) + n [ ∵ T(n/2) ≤ c(n/2)log(n/2) ]

= cn log (n/2) + n = cn log n + n - cn log 2 ≤ cn log n