마스터 정리

마스터 정리

마스터 정리는 특정한 모양을 가진 재귀식에 대해 바로 결과를 알 수 있는 아주 유용한 정리이다. 마스터 정리는 다음과 같은 모양을 가진 식에 적용된다.

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

즉, 입력 크기 n인 문제를 풀기 위해 입력 크기 n/b인 문제를 a개 풀고, 나머지 f(n)의 오버헤드가 필요한 알고리즘들이 해당된다. 아주 많은 알고리즘이 이에 해당되기 때문에, 마스터 정리는 아주 유용한 방법이다.

- 마스터 정리는 a >= 1, b > 1 에 대해 T(n) = a T(n/b) + f(n)인 점화식에서, n^(log(b) a) = h(n)이라고 할 때, T(n)의 점근적 복잡도를 다음의 기준에 따라 정의한다.

1) 어떤 양의 상수 e에 대해서, f(n)/h(n) = O(1/n^e)이라면, T(n) = Θ(h(n)) 이다.

2) 어떤 양의 상수 e에 대해서, f(n)/h(n) = Ω(n^e)이라면, T(n) = Θ(f(n))이다.

3) 어떤 양의 상수 e에 대해서, f(n)/h(n) = Θ(1) 이라면, T(n) = Θ(f(n) log n) 이다.

- 마스터 정리는 "T(n) = a T(n/b) + f(n)"의 형태가 아닌 점근식의 경우 성립되지 않는다. 그런 경우에는, 멱급수나 미적분등이 주로 사용된다.