英文原版不上了 直接中文
定义假设有递推关系式T(n)=aT(n/b)+f(n)
其中n为问题规模
a为递推的子问题数量
n/b为每个子问题的规模（假设每个子问题的规模基本一样）
f(n)为递推以外进行的计算工作，无需参加递归
a≥1，b>1为常数，f(n)为函数，T(n)为非负整数。则有以下结果（分类讨论）：
（1）若f(n)=O(nlogba-ε)存在ε>0，就是当nlogba的阶高于f(n)时，可以存在ε使得nlogba-ε和f(n)的阶相同。此时取T(n)=θ(nlogba)
（2）若f(n)=Θ(nlogba) 注意这时nlogba的阶和f(n)的阶相同，不需要ε。此时取T(n)=Θ(nlogbalogn)
（3）若f(n)=Ω(nlogba+ε)首先得存在ε>0，就是当nlogba的阶低于f(n)时，可以存在ε使得nlogba+ε和f(n)的阶相同,即有足够大的n，而当af(n/b)<=cf(n), c<1此时取T(n)=Θ(f(n))
定义二递推式子可以为T(n)=aT(n/b)+cnk 其中 cnk 表示原问题分解成子问题和将子问题的解合并成原问题的解的时间，对其分析可得到
\[T(n) = \begin{cases} O(n^{log_ba}) & a > b^k \\ O(n^k·log_bn) & a = b^k \\ O(n^k) & a < b^k \end{cases}\]