[Master Theorem] 마스터 이론(정리)

1. 일반적인 마스터 정리 T(n) = rT(n/c) + O(f(n))을 만족 하는 경우

3가지의 경우로 복잡도를 구할 수 있다.

2. 등차수열의 경우, T(n-2) + T(2) + O(n)과 같은 경우

3. 마스터정리를 만족하지 않는 경우, recursion tree를 그려서 복잡도를 구하는 경우

3_1. 만약 트리의 각 층의 너비가 같은 경우 : 트리의 높이 * 너비

3_2. 만약 트리의 너비가 작아질 경우 : 등비가 1보다 작은 등비수열의 합으로 표현가능, 즉 특정 상수에 수렴한다.

3_3. 만약 트리의 너비가 커질 경우 : 트리의 잎의 개수, (나누어지는 자식노드의 개수)^트리의 높이

 

3_2와 3_3의 예제. (algorithms-Jeff 49p 7번 의 (k), (l))

 

K(n).

공비가 1보다 작으므로, 결국 복잡도는 상수*n^2에 수렴하고, 이는 O(n^2)이다.

 

L(n).

반대로 공비가 1보다 커서 발산하는 경우이다.

O(4^(logn)), 이때의 트리의 높이는 트리가 비대칭이기 때문에 다 다르지만, 복잡도를 빅오로 나타낼 때, 상수는 무시할 수 있기 때문에 결국 logn의 높이를 가진다.

 

---

Add. 확장된 마스터 정리, 일반적인 마스터 정리로는 계산하기 어려운 경우 사용

https://coloredrabbit.tistory.com/94

마스터 정리 (+ 확장 마스터 정리)