[컴퓨터알고리즘] 4장 - (1) 점화식

4-1. Recurrence 점화식

 

분할정복기법

1. 분할, 2. 정복, 3. 결합

 

T(n) = { 1  // n = 1 (base case)

             T(n-1) + 1 // n > 1 (recursion case)

점화식의 해: T(n) = n

 

T(n) = { 1 // n =1 

             2T(n/2) + n // n > 1

점화식의 해: T(n) = nlgn + n

 

팩토리얼 예시

 

점화식의 관심사는 계산비용이다.

T(n) = aT(n/b) + D(n) + C(n)

* a개의 부분문제 (크기 n/b)

* D(n): 분할하는 비용

* C(n): 부분문제들의 답을 다시 결합하는 비용

재귀적 알고리즘들은 점화식으로 표현될 수 있다.

 

점화식을 푸는 3가지 방법

1. 치환법(Substitution)

- 추측 후, 옳음을 수학적 귀납법으로 증명한다.

2. 재귀 트리(Recursion-tree)

- 트리로 변환하고 합의 한계를 구한다.

3. 마스터 정리(Master)

- T(n) = aT(n/b) + f(n)

+) 충분히 작은 n에 대해 T(n) = Θ(1). T(n)이 상수라 가정한다.

 

1. 치환법

1) 형태를 추측한다. 2) 수학적 귀납법으로 증명한다.

 

예제 1

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

1. 이진탐색이랑 비슷하네? O(lgn)으로 추측.

2. T(n/2) = O(lg(n/2))으로 가정한다.

     Big O의 정의로부터 T(n/2) <= clg(n/2).

     T(n) = T(n/2) + d <= clg(n/2) + d = clgn - clg2 + d = clgn - c + d <= clgn.

     -c+d<=0 -> c>=d인 c 언제나 존재한다.

     따라서 if c>=d일때 만족한다.

 

예제 2

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

1. O(n^2)으로 추측.

2. T(n-1) = c(n-1)^2으로 가정한다.

     T(n) = c(n-1)^2 + n = cn^2 - 2cn + n + c <= cn^2

     c(-2n+1) + n <= 0. c(2n-1) >= n

     c >= n / (2n-1) = 1 / (2-1/n). 

     따라서 n>=1 인 경우 c>=1인 모든 c에 대하여 만족한다.

 

예제3

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

1. 마스터 정리

2. a=2, b=2. f(n) = n = n^(logba). 따라서 case 2. Θ(nlgn). O(nlgn)

 

2. 재귀 트리

치환법으로 추측이 어렵다면 재귀 트리를 그려 "각 레벨에서 발생하는 cost를 합한다."

1. 각 레벨에서 발생하는 cost 파악

2. 트리의 depth 파악

3. 단말 노드의 개수 파악

치환법을 적용해 답을 찾는다.

 

예제1

T(n) = 3T(n/4) + n^2

1. 각 레벨 cost:

     트리를 그려 확인해보니

     깊이 d일 때 (3/16)^d * cn^2

2. 트리의 depth:

     각 레벨에서 데이터의 크기가 4로 나뉘어진다. 1일때 단말 노드 n / 4^d = 1. d = log_4(n).

3. 단말 노드의 개수:

     한 depth에서 단말노드개수 3^d = 3^(log_4(n)) = n^(log_4(3))

Total cost:

     T(n) = cn^2 + ... + Θ(3^(log_4(n)) = O(n^2)

치환법, 마스터 정리로 계산할 수도 있다.

 

치환법으로 증명하기

T(n) = 3T(n/4) + n^2

1. O(n^2)로 추측

2. T(n/4) = c(n/4)^2.

    3c(n/4)^2 + n^2 = 3cn^2/16 + n^2

     = cn^2 - ( 13cn^2/16 - n^2 )

     <= cn^2.

     3cn^2/16 - n^2 >= 0이어야.

     따라서 c >= 16/13일 때 만족한다.

 

3. 마스터 정리

T(n) = aT(n/b) = f(n)

f(n)과 n^(log_b(a))를 대소비교.

- case 1, case 3: 큰 쪽의 Θ대로 시간복잡도, case 3에서는 af(n/b) <= cf(n) for c<1인 것을 증명해야 한다.

- case2: Θ(n^(log_b(a)) * logn)

 

예제들 풀어보기