마스터 정리

마스터 정리 (Master Theorem)는 분할 정복 알고리즘의 시간 복잡도를 점근적으로 분석하는 데 사용되는 정리이다. 특히 재귀 호출의 크기가 동일하고 각 단계에서 발생하는 추가적인 작업량이 다항 함수로 표현될 수 있을 때 유용하게 적용된다.

마스터 정리는 다음과 같은 형태의 점화식으로 표현되는 알고리즘의 시간 복잡도를 분석하는 데 사용된다.

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

여기서:

• T(n)은 크기가 n인 문제에 대한 알고리즘의 시간 복잡도이다.
• a는 각 문제에서 생성되는 하위 문제의 수이다. (a ≥ 1)
• n/b는 각 하위 문제의 크기이다. (b > 1)
• f(n)은 문제 분할 및 하위 문제 결합에 소요되는 작업량이다.

마스터 정리는 a, b, 그리고 f(n)의 점근적 성장률에 따라 세 가지 경우로 나뉜다. 각 경우에 따라 T(n)의 점근적 복잡도를 결정하는 방법이 제시된다.

마스터 정리의 세 가지 경우:

1. 경우 1: f(n) = O(nlogb(a) - ε) for some constant ε > 0인 경우, T(n) = Θ(nlogb(a))이다. 즉, f(n)이 nlogb(a)보다 점근적으로 작으면, 시간 복잡도는 재귀 호출에 의해 지배된다.

2. 경우 2: f(n) = Θ(nlogb(a))인 경우, T(n) = Θ(nlogb(a) log n)이다. 즉, f(n)과 nlogb(a)가 점근적으로 같으면, 시간 복잡도는 재귀 호출과 추가 작업량의 조합에 의해 결정된다.

3. 경우 3: f(n) = Ω(nlogb(a) + ε) for some constant ε > 0이고 af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n인 경우, T(n) = Θ(f(n))이다. 즉, f(n)이 nlogb(a)보다 점근적으로 크면, 시간 복잡도는 추가 작업량에 의해 지배된다. (이때 정규성 조건 af(n/b) ≤ cf(n)을 만족해야 한다.)

마스터 정리의 활용 예시:

• 병합 정렬 (Merge Sort): T(n) = 2T(n/2) + Θ(n). a=2, b=2, f(n) = Θ(n)이다. nlogb(a) = nlog2(2) = n 이므로 경우 2에 해당하며, T(n) = Θ(n log n)이다.

• 이진 탐색 (Binary Search): 마스터 정리를 직접 적용하기는 어렵지만, 유사한 분석을 통해 시간 복잡도를 유추할 수 있다.

주의사항:

마스터 정리는 모든 형태의 점화식에 적용될 수 있는 것은 아니다. 특히 f(n)이 다항 함수 형태로 표현되지 않거나, 위의 세 가지 경우에 정확히 부합하지 않는 경우에는 다른 방법을 사용하여 시간 복잡도를 분석해야 한다. 재귀 트리 방법이나 대체 방법 등을 사용할 수 있다.