쉽게 배우는 알고리즘 2장 요약

2장. 점화식과 점근적 복잡도 분석

1. 점화식의 이해

점화식: 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법

-> 등차수열, factorial, 피보나치 수열

예)

재귀적 관계를 이용해 알고리즘의 수행시간을 점화식으로 표현할 수 있다.

병합정렬의 경우 "T(n) = 2T(n/2) + 후처리시간"으로 표현할 수 있다.

2. 점화식의 점근적 분석 방법

a. 반복 대치

T(n)을 T(n-1)로 대치하고 T(n-1)을 T(n-2)로 대치하고 계속해서 T(n-2), T(n-3), ..., T(1)까지 반복해서 대치해가는 것과 같은 방식을 사용해 점근적 복잡도를 구한다.

b. 추정후 증명

식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옮음을 귀납적으로 증명하는 방법

c. 마스터 정리

a>=1, b>1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^(log a over b) = h(n)이라 할 때 T(n)의 점근적 복잡도는 아래와 같다.

- 어떤 양의 상수 e에 대하여 f(n)/h(n) = O(1/(n^e))이면, T(n) = Theta(h(n))이다.

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

- f(n)/h(n) = Theta(1)이면 T(n) = Theta(h(n)log n)이다.