마스터 정리 문서 원본 보기

{{위키데이터 속성 추적}}
알고리즘 분석에서 '''The Master Method'''(마스터 방법, 만능 방법), '''{{lang|en|Master Theorem}}'''(마스터 정리)는 [[재귀 관계식]]으로 표현한 [[알고리즘]]의 동작 시간을 [[점근 표기법|점근적]]으로 계산하여 간단하게 계산하는 방법이다.

잘 알려진 알고리즘 교과서 ''[[Introduction to Algorithms]]''의 4.3절과 4.4절, '''4.5절'''에 설명되어 유명해졌으나, 이 방법이 모든 재귀 관계식을 풀 수 있는 건 아니다.

다음과 같은 관계식이 주어졌다고 하자.

:<math>
T(n) = 
\begin{cases}
\Theta(1) & \mathrm{if}\quad n=1\\
aT(n/b) + f(n) & \mathrm{otherwise}
\end{cases}
</math>

여기서 <math>\scriptstyle a \geq 1, b > 1</math>이고 <math>f(n)</math>은 점근적으로 양수 함수값을 가지는 함수이다. 이때 다음과 같은 경우에 대해 점근적 수행 시간을 계산할 수 있다.

# 만약 어떤 상수 <math>\scriptstyle \epsilon > 0</math>에 대해 <math>\scriptstyle f(n) \in O\left( n^{\log_b a - \epsilon} \right)</math>이면, <math>\scriptstyle T(n) \in \Theta\left( n^{\log_b a} \right)</math>이다.
# 만약 <math>\scriptstyle f(n) \in \Theta\left( n^{\log_b a} \right)</math>이면, <math>\scriptstyle T(n) \in \Theta\left( n^{\log_b a} \log{n}\right)</math>이다.
# 만약 어떤 상수 <math>\scriptstyle \epsilon > 0</math>에 대해 <math>\scriptstyle f(n) \in \Omega\left( n^{\log_b a + \epsilon} \right)</math>이고, <math>c < 1</math>과 충분히 큰 <math>n</math>에 대해 <math>\scriptstyle a f\left( \frac{n}{b} \right) \le c f(n)</math>이 성립하면, <math>\scriptstyle T(n) \in \Theta(f(n))</math>이다.

== 외부 링크 ==
* {{언어링크|en}} [http://mitpress.mit.edu/algorithms/ ''알고리즘 소개'']

{{토막글|컴퓨터 과학}}

[[분류:알고리즘]]
[[분류:점근 해석]]
[[분류:수학 정리]]
[[분류:점화식]]