# 主定理

## 支配理论

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$，其中 ${\displaystyle a\geq 1{\mbox{, }}b>1}$

### 情形一

${\displaystyle f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right)}$（可不严谨的视作多项式地小于）

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}$

### 情形二

${\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon }n\right)}$

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon +1}n\right)}$

### 情形三

${\displaystyle f(n)=\Omega \left(n^{\log _{b}(a)+\epsilon }\right)}$（多项式地大于）

${\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}$

${\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}$

## 参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.