마스터 정리
마스터 정리(Master Theorem)는 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 사용되는 수학적 정리이다. 주어진 재귀 관계식을 일반적인 형태로 변환하여 알고리즘의 실행 시간을 평가할 수 있도록 도와준다.
개요[편집 | 원본 편집]
마스터 정리는 특정 유형의 재귀 관계식을 해결하는 방법을 제공하며, 특히 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 유용하다. 이 정리는 다음과 같은 형태의 점화식을 해석하는 데 사용된다.
<math> T(n) = aT(n/b) + f(n) </math>
여기서
- a : 하위 문제의 개수
- b : 입력 크기 축소 비율
- f(n) : 추가적인 작업(주어진 단계에서 수행하는 연산)
마스터 정리를 사용하면 위와 같은 점화식을 세 가지 경우로 나누어 시간 복잡도를 분석할 수 있다.
마스터 정리의 세 가지 경우[편집 | 원본 편집]
마스터 정리는 다음과 같은 세 가지 경우(case)로 나뉜다.
- Case 1: f(n) = O(n^c) 이고, c < log_b(a)
- 대부분의 연산이 하위 문제에서 발생하며, 전체 시간 복잡도는 재귀 호출에 의해 결정된다.
- 결과: <math> T(n) = O(n^{\log_b a}) </math>
- Case 2: f(n) = Θ(n^c) 이고, c = log_b(a)
- 하위 문제와 추가 연산의 기여도가 비슷하며, 전체 시간 복잡도는 이 두 요소에 의해 균형을 이룬다.
- 결과: <math> T(n) = O(n^c \log n) </math>
- Case 3: f(n) = O(n^c) 이고, c > log_b(a)
- 대부분의 연산이 재귀 호출 외부에서 발생하며, 추가 연산이 전체 시간 복잡도를 결정한다.
- 결과: <math> T(n) = O(f(n)) = O(n^c) </math>
예제[편집 | 원본 편집]
다음은 마스터 정리를 사용하여 시간 복잡도를 분석하는 예제이다.
예제 1: 병합 정렬[편집 | 원본 편집]
병합 정렬(Merge Sort)의 시간 복잡도는 다음과 같은 재귀 관계식을 따른다.
<math> T(n) = 2T(n/2) + O(n) </math>
이를 마스터 정리의 형태와 비교하면,
- a = 2
- b = 2
- f(n) = O(n)
- log_b(a) = log_2(2) = 1
여기서 f(n) = O(n)이고, log_b(a) = 1이므로 Case 2에 해당한다. 따라서 병합 정렬의 시간 복잡도는 다음과 같이 계산된다.
<math> T(n) = O(n \log n) </math>
예제 2: 거듭 제곱(빠른 제곱법)[편집 | 원본 편집]
거듭 제곱(Exponentiation by Squaring) 알고리즘의 시간 복잡도는 다음과 같다.
<math> T(n) = T(n/2) + O(1) </math>
여기서
- a = 1
- b = 2
- f(n) = O(1)
- log_b(a) = log_2(1) = 0
f(n) = O(1)이고 log_b(a) = 0이므로 Case 1에 해당한다. 따라서 거듭 제곱 알고리즘의 시간 복잡도는 다음과 같다.
<math> T(n) = O(\log n) </math>
마스터 정리의 적용 조건[편집 | 원본 편집]
마스터 정리는 모든 재귀 관계식에 적용될 수 있는 것은 아니다. 다음과 같은 조건이 만족되어야 한다.
- 점화식이 <math> T(n) = aT(n/b) + f(n) </math> 형태를 가져야 한다.
- a ≥ 1, b > 1인 양의 정수여야 한다.
- f(n)이 다항 함수(Polynomial Function) 형태여야 한다.
이 조건을 만족하지 않는 경우, 반복적 점화 관계 풀이(Recursion Tree Method) 또는 점근적 주요 항 분석(Asymptotic Analysis) 등의 다른 방법을 사용해야 한다.
같이 보기[편집 | 원본 편집]
참고 문헌[편집 | 원본 편집]
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.