마스터 정리

마스터 정리(Master Theorem)는 분할 정복법(Divide and Conquer)을 사용한 알고리즘의 시간 복잡도를 계산하는 데 유용한 수학적 도구이다. 이 정리는 재귀적 알고리즘의 시간 복잡도를 분석하는 데 사용되며, 특히 재귀식이 다음과 같은 형태로 주어졌을 때 적용할 수 있다.

1 정의

마스터 정리는 다음과 같은 형태의 재귀식을 분석하는 데 사용된다:

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

여기서,

• T(n): 문제 크기가 n일 때의 전체 시간 복잡도
• a: 문제를 분할하는 횟수 (즉, 자식 문제의 수)
• b: 각 자식 문제의 크기 비율 (b > 1)
• f(n): 분할된 문제의 결과를 합치거나 추가적으로 수행하는 작업의 복잡도

마스터 정리는 f(n)의 성장 속도와 n^log_ba의 상대적인 크기에 따라 세 가지 경우로 나뉜다.

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

2.1 경우 1 (분할이 지배적인 경우)

• f(n) = O(n^c) 이고 c < log_ba 인 경우
  • 전체 시간 복잡도: T(n) = Θ(n^log_ba)
  • 이 경우는 f(n)이 n^log_ba보다 느리게 증가하므로, 전체 작업의 대부분은 재귀적으로 분할된 부분 문제에서 발생한다.

2.2 경우 2 (균형적인 경우)

• f(n) = Θ(n^log_ba) 인 경우
• 전체 시간 복잡도: T(n) = Θ(n^log_ba log n)

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

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

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

• 전체 시간 복잡도: T(n) = Θ(f(n))

• 이 경우는 f(n)이 n^log_ba보다 빠르게 증가하고, 정규성 조건까지 만족할 경우 전체 작업량은 f(n)이 지배하게 된다.

3 예제

3.1 예제 1

T(n) = 10T(n / 10) + log10n

• a = 10, b = 10 → n^log₁₀10 = n¹
• f(n) = log¹⁰n = o(n^1−ε) → 경우 1
• 정답: Θ(n)

3.2 예제 2

T(n) = 100T(n / 10) + n10

• a = 100, b = 10 → n^log₁₀100 = n²
• f(n) = n¹⁰ = ω(n^{2 + ε}), 정규성 조건 만족 → 경우 3
• 정답: Θ(n¹⁰)

3.3 예제 3

T(n) = 10T(n / 100) + (log n)log log n

• a = 10, b = 100 → n^{log₁₀₀10} = n^0.5
• f(n) = (log n)^{log log n} = o(n^ε) for all ε > 0
• f(n) = o(n^0.5) → 경우 1
• 정답: Θ(n^0.5)

3.4 예제 4

T(n) = 16T(n / 4) + 4log n = 16T(n / 4) + n2*a = 16, b = 4 → nlog416 = n2

• f(n) = n² = Θ(n²) → 경우 2
• 정답: Θ(n² log n)

3.5 예제 5

T(n) = 3T(n / 8) + 1

• a = 3, b = 8, f(n) = 1 = Θ(1)
• n^log₈3 ≈ n^0.528
• f(n) = O(n^log₈3 − ε) → 경우 1
• 정답: Θ(n^log₈3)

3.6 예제 6

T(n) = 3T(n / 8) + √n · log n

• a = 3, b = 8, f(n) = n^0.5 log n
• n^log₈3 ≈ n^0.528
• f(n) = o(n^log₈3) → 경우 1
• 정답: Θ(n^log₈3)

3.7 예제 7

T(n) = 18T(n / 3) + n3*a = 18, b = 3 → nlog318 ≈ n2.63

• f(n) = ω(n^2.63), 정규성 조건 만족 → 경우 3
• 정답: Θ(n³)

3.8 예제 8

T(n) = 27T(n / 3) + n3

• a = 27, b = 3 → n^log₃27 = n³
• f(n) = Θ(n³) → 경우 2
• 정답: Θ(n³ log n)

3.9 예제 9

T(n) = 18T(n / 3) + n2 · log n

• a = 18, b = 3 → n^log₃18 ≈ n^2.63
• f(n) = o(n^2.63) → 경우 1
• 정답: Θ(n^log₃18)

3.10 예제 10

T₁(n) = 8T₁(n / 4) + n1.5

• a = 8, b = 4 → n^log₄8 = n^1.5
• f(n) = Θ(n^1.5) → 경우 2
• 정답: Θ(n^1.5 log n)

3.11 예제 11

T₂(n) = 6T₂(n / 3) + n2

• a = 6, b = 3 → n^log₃6 ≈ n^1.63
• f(n) = ω(n^1.63), 정규성 조건 만족 → 경우 3
• 정답: Θ(n²)

3.12 예제 12

T(n) = 3T(n / 25) + log3n

• a = 3, b = 25 → n^log₂₅3 ≈ n^0.396
• f(n) = log³n = o(n^0.396) → 경우 1
• 정답: Θ(n^log₂₅3)

3.13 예제 13

T(n) = 8T(n / 2) + n3 log3n

• a = 8, b = 2 → n^log₂8 = n³
• f(n) = n³ log³n = ω(n³), 정규성 조건 만족 → 경우 3
• 정답: Θ(n³ log³n)

3.14 예제 14

T(n) = 25T(n / 3) + (n / log n)3

• a = 25, b = 3 → n^{log_b a} = n^{log₃ 25} ≈ n^2.929
• f(n) = (n/log n)³ = Ω(n^{2.929 + ε}) → 경우 3
• 정답: Θ((n/log n)³)

3.15 예제 15

T(n) = 4T(n / 15) + √n*a = 4, b = 15 → nlog154 ≈ n0.504

• f(n) = √n = n^0.5 = o(n^0.504) → 경우 1
• 정답: Θ(n^log₁₅4)

3.16 예제 16

T(n) = 15T(n / 4) + (n / log n)2

• a = 15, b = 4 → n^log₄15 ≈ n^1.953
• f(n) = (n / log n)² = ω(n^1.953), 정규성 조건 만족 → 경우 3
• 정답: Θ((n / log n)²)

4 응용

마스터 정리는 다양한 알고리즘의 시간 복잡도를 분석하는 데 활용된다. 대표적인 예시는 다음과 같다.

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

5 같이 보기

• 분할 정복법
• 재귀 알고리즘
• 시간 복잡도
• 퀵 정렬
• 합병 정렬
• 반복 치환법

6 참고 문헌

• 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.