알고리즘 분석에서 The Master Method(마스터 방법, 만능 방법), Master Theorem(마스터 정리)는 재귀 관계식으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법이다.
잘 알려진 알고리즘 교과서 Introduction to Algorithms의 4.3절과 4.4절, 4.5절에 설명되어 유명해졌으나, 이 방법이 모든 재귀 관계식을 풀 수 있는 건 아니다.
다음과 같은 관계식이 주어졌다고 하자.
![{\displaystyle T(n)={\begin{cases}\Theta (1)&\mathrm {if} \quad n=1\\aT(n/b)+f(n)&\mathrm {otherwise} \end{cases}}}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8PoNa5oqhDnjnCaNBFnDFFaqo0aAe5aDnAnjGPngi4nqi1nAsOztK2)
여기서
이고
은 점근적으로 양수 함수값을 가지는 함수이다. 이때 다음과 같은 경우에 대해 점근적 수행 시간을 계산할 수 있다.
- 만약 어떤 상수
에 대해
이면,
이다.
- 만약
이면,
이다.
- 만약 어떤 상수
에 대해
이고,
과 충분히 큰
에 대해
이 성립하면,
이다.