마스터 정리

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

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

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

$T(n)=\{\begin{array}{cc}\mathrm{\Theta }(1)& \mathrm{i}\mathrm{f}n=1\\ aT(n/b)+f(n)& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$

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

1. 만약 어떤 상수 $ϵ>0$에 대해 $f(n)\in O\left(n^{{\log }_{b}a-ϵ}\right)$이면, $T(n)\in \mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$이다.
2. 만약 $f(n)\in \mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$이면, $T(n)\in \mathrm{\Theta }(n^{{\log }_{b}a}\log n)$이다.
3. 만약 어떤 상수 $ϵ>0$에 대해 $f(n)\in \mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$이고, $c<1$과 충분히 큰 $n$에 대해 $af\left(\frac{n}{b}\right)\le cf(n)$이 성립하면, $T(n)\in \mathrm{\Theta }(f(n))$이다.

외부 링크

• 틀:언어링크 알고리즘 소개