마스터 정리 편집하기

'''마스터 정리'''(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.