1.4 마스터 정리
마스터 정리(master theorem)는 다음과 같은 재귀 관계식의 동작 시간을 점근적으로 계산하는 방법입니다.
a ≥ 1이고 b > 1일 때, T(n) = aT(n/b) + f(n)
이때 n은 문제의 크기고, a는 재귀에서 하위 문제의 개수이며, n/b는 각 하위 문제의 크기입니다. f(n)은 문제를 하위 문제로 나누고 그 하위 문제의 결과를 최종 결과로 다시 합칠 때 드는 비용입니다.
다음 세 가지 경우에서 점근적 근접 한계값을 결정할 수 있습니다.
• 사례 1 f(n) = O(nlogba-∈)이고 상수 Є > 1일 때, 최종 시간 복잡도 T(n) = Θ(nlogba)입니다.
• 사례 2 f(n) = Θ(nlogbalogkn)이고 상수 k ≥ 0일 때, 최종 시간 복잡도 T(n) = Θ(nlogba logk+1n)입니다.
• 사례 3 f(n) = Ω(nlogba+∈)이고 상수 Є > 1일 때, 최종 시간 복잡도 T(n) = Θ(f(n))입니다.
▲ 그림 1-4 점근적 근접 한계값