알고리즘...7

- 추정후 증명

추정후 증명은 식의 모양을 보고 점근적 복잡도를 추정한 뒤 그것이 옳음을 증명하는 방법으로 추정을 의미 있게 하는 것이 중요하다. 이때, 적절한 추정을 위해서는 여러 식을 분석하고 결과를 얻는 과정을 반복해 직관을 얻어야 한다.

 

※ 추정을 너무 크게 한다면 의미가 없는 결과를 얻게 되고 추정을 너무 작게 한다면 증명이 불가능하다.

 

- 마스터 정리

마스터 정리는 다음과 같은 모양을 가진 재귀식에 대해 결과를 바로 알 수 있는 정리이다.

 

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

 

1. 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ο(1/n^ε)이면, T(n)=Θ(h(n))이다.
2. 어떤 양의 상수 ε에 대하여 f(n)/(h(n) = Ω(n^ε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 af(n/b) ≤ c(fn)이면 T(n) = Θ(f(n))이다.
3. f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) logn)이다.

 

마스터 정리를 특정 조건에서 근사한 것은 다음과 같다.

a ≥ 1, b ＞ 1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^log_ba = h(n)이라 할 때 T(n)의 개략적인 점근적 복잡도는 다음과 같다.

1. lim_n->∞ f(n)/h(n) = 0 이면 T(n) = Θ(h(n))이다.
2. lim_n->∞ f(n)/h(n) = ∞이고, 충분히 큰 모든 n에 대해 af(n/b) ＜ f(n)이면 T(n) = Θ(f(n))이다.
3. f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) logn)이다.

 

※ 마스터 정리와 근사 버전은 정확히 일치하는 것이 아니다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘