마스터 정리 편집하기

'''마스터 정리'''(Master Theorem)는 분할 정복법(Divide and Conquer)을 사용한 알고리즘의 시간 복잡도를 계산하는 데 유용한 수학적 도구이다. 이 정리는 재귀적 알고리즘의 시간 복잡도를 분석하는 데 사용되며, 특히 재귀식이 다음과 같은 형태로 주어졌을 때 적용할 수 있다.
==정의==
마스터 정리는 다음과 같은 형태의 재귀식을 분석하는 데 사용된다:
 T(n) = aT(n / b) + f(n)
여기서,
*T(n): 문제 크기가 n일 때의 전체 시간 복잡도
*a: 문제를 분할하는 횟수 (즉, 자식 문제의 수)
*b: 각 자식 문제의 크기 비율 (b > 1)
*f(n): 분할된 문제의 결과를 합치거나 추가적으로 수행하는 작업의 복잡도
마스터 정리는 f(n)의 성장 속도와 <big>n<sup>log<sub>b</sub>a</sup></big>의 상대적인 크기에 따라 세 가지 경우로 나뉜다.
==마스터 정리의 세 가지 경우==
===경우 1 (분할이 지배적인 경우)===
*<big>'''f(n) = O(n<sup>c</sup>) 이고 c < log<sub>b</sub>a 인 경우'''</big>
**전체 시간 복잡도: <big>T(n) = Θ(n<sup>log<sub>b</sub>a</sup>)</big>
**이 경우는 f(n)이 n<sup>log<sub>b</sub>a</sup>보다 느리게 증가하므로, 전체 작업의 대부분은 재귀적으로 분할된 부분 문제에서 발생한다.
===경우 2 (균형적인 경우)===
*<big>'''f(n) = Θ(n<sup>log<sub>b</sub>a</sup>) 인 경우'''</big>
*전체 시간 복잡도: <big>T(n) = Θ(n<sup>log<sub>b</sub>a</sup> log n)</big>

* 이 경우는 분할과 추가 작업 비용이 같은 수준이므로, 로그 항이 하나 추가된다.

=== 경우 3 (추가 작업이 지배적인 경우) ===

* '''<big>f(n) = Ω(n<sup>c</sup>) 이고 c > log<sub>b</sub>a 인 경우</big>'''
* 그리고 다음 정규성 조건이 만족되어야 한다
** <big>a·f(n/b) ≤ c·f(n)</big> (어떤 상수 c < 1에 대해, 충분히 큰 n에서 항상 성립)

*전체 시간 복잡도: <big>T(n) = Θ(f(n))</big>

* 이 경우는 f(n)이 n<sup>log<sub>b</sub>a</sup>보다 빠르게 증가하고, 정규성 조건까지 만족할 경우 전체 작업량은 f(n)이 지배하게 된다.

==예제==
===예제 1===
 T(n) = 10T(n / 10) + log<sup>10</sup>n
*a = 10, b = 10 → n<sup>log<sub>10</sub>10</sup> = n<sup>1</sup>
*f(n) = log<sup>10</sup>n = o(n<sup>1−ε</sup>) → 경우 1
*정답: Θ(n)
=== 예제 2===
 T(n) = 100T(n / 10) + n<sup>10</sup>
* a = 100, b = 10 → n<sup>log<sub>10</sub>100</sup> = n<sup>2</sup>
* f(n) = n<sup>10</sup> = ω(n<sup>2 + ε</sup>), 정규성 조건 만족 → 경우 3
*정답: Θ(n<sup>10</sup>)
===예제 3===
 T(n) = 10T(n / 100) + (log n)<sup>log log n</sup>
*a = 10, b = 100 → n<sup>log<sub>100</sub>10</sup> = n<sup>0.5</sup>
*f(n) = (log n)<sup>log log n</sup> = o(n<sup>ε</sup>) for all ε > 0
*f(n) = o(n<sup>0.5</sup>) → 경우 1
* 정답: Θ(n<sup>0.5</sup>)
===예제 4===
 T(n) = 16T(n / 4) + 4<sup>log n</sup> = 16T(n / 4) + n<sup>2</sup>*a = 16, b = 4 → n<sup>log<sub>4</sub>16</sup> = n<sup>2</sup>
*f(n) = n<sup>2</sup> = Θ(n<sup>2</sup>) → 경우 2
*정답: Θ(n<sup>2</sup> log n)
===예제 5===
 T(n) = 3T(n / 8) + 1
*a = 3, b = 8, f(n) = 1 = Θ(1)
*n<sup>log<sub>8</sub>3</sup> ≈ n<sup>0.528</sup>
*f(n) = O(n<sup>log<sub>8</sub>3</sup> − ε) → 경우 1
*정답: Θ(n<sup>log<sub>8</sub>3</sup>)
===예제 6===
 T(n) = 3T(n / 8) + √n · log n
*a = 3, b = 8, f(n) = n<sup>0.5</sup> log n
*n<sup>log<sub>8</sub>3</sup> ≈ n<sup>0.528</sup>
*f(n) = o(n<sup>log<sub>8</sub>3</sup>) → 경우 1
*정답: Θ(n<sup>log<sub>8</sub>3</sup>)
===예제 7===
 T(n) = 18T(n / 3) + n<sup>3</sup>*a = 18, b = 3 → n<sup>log<sub>3</sub>18</sup> ≈ n<sup>2.63</sup>
*f(n) = ω(n<sup>2.63</sup>), 정규성 조건 만족 → 경우 3
*정답: Θ(n<sup>3</sup>)
===예제 8 ===
 T(n) = 27T(n / 3) + n<sup>3</sup>
*a = 27, b = 3 → n<sup>log<sub>3</sub>27</sup> = n<sup>3</sup>
*f(n) = Θ(n<sup>3</sup>) → 경우 2
*정답: Θ(n<sup>3</sup> log n)
===예제 9===
 T(n) = 18T(n / 3) + n<sup>2</sup> · log n
*a = 18, b = 3 → n<sup>log<sub>3</sub>18</sup> ≈ n<sup>2.63</sup>
*f(n) = o(n<sup>2.63</sup>) → 경우 1
*정답: Θ(n<sup>log<sub>3</sub>18</sup>)
===예제 10 ===
 T₁(n) = 8T₁(n / 4) + n<sup>1.5</sup>
*a = 8, b = 4 → n<sup>log<sub>4</sub>8</sup> = n<sup>1.5</sup>
*f(n) = Θ(n<sup>1.5</sup>) → 경우 2
*정답: Θ(n<sup>1.5</sup> log n)
===예제 11 ===
 T₂(n) = 6T₂(n / 3) + n<sup>2</sup>
*a = 6, b = 3 → n<sup>log<sub>3</sub>6</sup> ≈ n<sup>1.63</sup>
*f(n) = ω(n<sup>1.63</sup>), 정규성 조건 만족 → 경우 3
*정답: Θ(n<sup>2</sup>)
===예제 12===
 T(n) = 3T(n / 25) + log<sup>3</sup>n
* a = 3, b = 25 → n<sup>log<sub>25</sub>3</sup> ≈ n<sup>0.396</sup>
*f(n) = log<sup>3</sup>n = o(n<sup>0.396</sup>) → 경우 1
*정답: Θ(n<sup>log<sub>25</sub>3</sup>)
===예제 13===
 T(n) = 8T(n / 2) + n<sup>3</sup> log<sup>3</sup>n
*a = 8, b = 2 → n<sup>log<sub>2</sub>8</sup> = n<sup>3</sup>
*f(n) = n<sup>3</sup> log<sup>3</sup>n = ω(n<sup>3</sup>), 정규성 조건 만족 → 경우 3
* 정답: Θ(n<sup>3</sup> log<sup>3</sup>n)
===예제 14===
 T(n) = 25T(n / 3) + (n / log n)<sup>3</sup>
*a = 25, b = 3 → n<sup>log<sub>b</sub> a</sup> = n<sup>log<sub>3</sub> 25</sup> ≈ n<sup>2.929</sup> 
*f(n) = (n/log n)<sup>3</sup> = Ω(n<sup>2.929 + ε</sup>) → 경우 3 
*정답: Θ((n/log n)<sup>3</sup>)
===예제 15===
 T(n) = 4T(n / 15) + √n*a = 4, b = 15 → n<sup>log<sub>15</sub>4</sup> ≈ n<sup>0.504</sup>
*f(n) = √n = n<sup>0.5</sup> = o(n<sup>0.504</sup>) → 경우 1
*정답: Θ(n<sup>log<sub>15</sub>4</sup>)
===예제 16===
 T(n) = 15T(n / 4) + (n / log n)<sup>2</sup>
*a = 15, b = 4 → n<sup>log<sub>4</sub>15</sup> ≈ n<sup>1.953</sup>
*f(n) = (n / log n)<sup>2</sup> = ω(n<sup>1.953</sup>), 정규성 조건 만족 → 경우 3
*정답: Θ((n / log n)<sup>2</sup>)
== 응용 ==
마스터 정리는 다양한 알고리즘의 시간 복잡도를 분석하는 데 활용된다. 대표적인 예시는 다음과 같다.

* '''합병 정렬(Merge Sort)'''
** 재귀식: T(n) = 2T(n / 2) + O(n)
** 시간 복잡도: O(n log n)
* '''퀵 정렬(Quick Sort)'''
** 평균 시간 복잡도: O(n log n)
** 최악 시간 복잡도: O(n<sup>2</sup>) (분할이 불균형할 때)
* '''행렬 곱셈(Matrix Multiplication)'''
** Strassen 알고리즘의 경우: T(n) = 7T(n / 2) + O(n^2)
** 시간 복잡도: O(n^log₇(7)) ≈ O(n<sup>2.81</sup>)

== 같이 보기 ==
* [[분할 정복법]]
* [[재귀 알고리즘]]
* [[시간 복잡도]]
* [[퀵 정렬]]
* [[합병 정렬]]
* [[반복 치환법]]

== 참고 문헌 ==
* Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
* Knuth, Donald. "The Art of Computer Programming, Volume 3: Sorting and Searching." Addison-Wesley, 1998.
[[Category:수학]]