(摘自《算法导论》)
主定理:
若T(n)由递归式T(n)=aT(n/b)+f(n)对非负整数定义,其中a≥1,b>1为常数,f(n)为一函数,则:
\[T(n) = \left\{ \begin{array}{l}
\Theta ({n^{{{\log }_b}a}}),\exists \varepsilon > 0,f(n) = O({n^{{{\log }_b}a - \varepsilon }})\\
\Theta ({n^{{{\log }_b}a}}\lg n),f(n) = \Theta ({n^{{{\log }_b}a}})\\
\Theta (f(n)),\exists \varepsilon > 0,f(n) = \Omega {\kern 1pt} ({n^{{{\log }_b}a + \varepsilon }}){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} and{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \exists c < 1,{n_0} > 0,for{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} n > {n_0},af(n/b) \le cf(n)
\end{array} \right.\]
注意: \[主定理并不能解决所有形如T(n)=aT(n/b)+f(n)的问题,在第1,3种情况,f(n)必须多项式地小于(大于){n^{{{\log }_b}a}},即f(n)和{n^{{{\log }_b}a}}之间差{n^\varepsilon }以上\]
例如:T(n)=2T(n/2)+nlogn,虽然nlogn=Ω(n),但找不到一个ε满足:
\[f(n) = n\log n = \Omega ({n^{{{\log }_b}a - \varepsilon }}) = \Omega ({n^{1 - \varepsilon }})\]
也就是说,
\[f(n)/{n^{{{\log }_b}a}}{\rm{渐进小于}}{n^\varepsilon }\]
处于第2和第3种情况之间,此时不能使用主定理.
原文：http://www.cnblogs.com/reasno/p/4897600.html