마스터 정리

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

1 정의

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

• T(n) = aT(n / b) + O(n^d)

여기서:

• T(n)은 문제 크기가 n일 때의 시간 복잡도.
• a는 문제를 분할하는 횟수 (즉, 자식 문제의 수).
• b는 각 자식 문제의 크기 비율.
• d는 각 분할된 문제에 대해 수행하는 작업의 복잡도.

마스터 정리는 이 재귀식의 해결 방법을 세 가지 경우로 나눈다.

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

마스터 정리의 핵심은 주어진 문제의 재귀식을 분석하여, 아래의 세 가지 경우에 맞는 결과를 도출하는 것이다.

경우 1 (a > b^d)

• 만약 a > b^d이면, 전체 시간 복잡도는 T(n) = O(n^log(b)a)이다.
• 즉, 재귀 문제의 분할이 더 큰 비율로 발생하며, 이때의 시간 복잡도는 자식 문제의 크기가 감소하는 것보다 주어진 작업에서의 시간 복잡도가 더 중요하다.

경우 2 (a = b^d)

• 만약 a = b^d이면, 전체 시간 복잡도는 T(n) = O(n^{d log n})이다.
• 이 경우는 자식 문제의 크기 감소와 주어진 작업에서의 복잡도가 동일하게 영향을 미친다. 이때의 복잡도는 log n을 추가하여 계산된다.

경우 3 (a < b^d)

• 만약 a < b^d이면, 전체 시간 복잡도는 T(n) = O(n^d)이다.
• 이 경우는 자식 문제의 크기 감소가 주어진 작업에서의 복잡도보다 더 중요하므로, 문제를 더 작은 크기로 분할하는 것이 중요하다.

예제

다음은 마스터 정리를 적용한 몇 가지 예제이다.

예제 1

T(n) = 2T(n / 2) + O(n)

여기서 a = 2, b = 2, d = 1 이다. 따라서 a = b^d이므로, 경우 2가 적용되고 시간 복잡도는:

• T(n) = O(n log n)

예제 2

T(n) = 3T(n / 4) + O(n)

여기서 a = 3, b = 4, d = 1 이다. a < b^d이므로, 경우 3이 적용되고 시간 복잡도는:

• T(n) = O(n)

예제 3

T(n) = 4T(n / 2) + O(n²)

여기서 a = 4, b = 2, d = 2 이다. a = b^d이므로, 경우 2가 적용되고 시간 복잡도는:

• T(n) = O(n^{2 log n})

응용

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

• 합병 정렬(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)

같이 보기

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

참고 문헌

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