# 主定理

## 主定理

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

### 情形一

$f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$，并且是多项式的小于

$T(n) = \Theta\left( n^{\log_b a} \right)$

### 情形二

$f(n) = \Theta\left( n^{\log_b a} \log^{k} n \right)$

$T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n \right)$

### 情形三

$f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right)$，并且是多项式的大于

$a f\left( \frac{n}{b} \right) \le c f(n)$

$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.