在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n)，本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论，以期望找出通用的递归方程的求解方式。

算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况，根据Master定理：o-渐进上界、w-渐进下界、O-渐进确界。

设a≥1，b＞1为常数，f(n)为函数，T(n)=aT(n/b)+f(n)为非负数,令x=log_ba：

1. f(n)=o(n^x-e)，e＞0，那么T(n)=O(n^x)。

2. f(n)=O(n^x)，那么T(n)=O(n^x logn)。

3. f(n)=w(n^x+e)，e＞0且对于某个常数c＜1和所有充分大的n有af(n/b)≤cf(n)，那么T(n)=O(f(n))。

然而，Master定理并没有完全包括所有的f(n)的情况。注意到条件1和3中的e总是大于0的，所以在条件1和2、条件2和3之间存在所谓的“间隙”，使得某些f(n)在该情况下不能使用该定理。因此，我们需要找到在Master定理不能使用的情况下如何解递归方程的比较通用的办法——递归树。

经过分析，递归树解法包含了Master定理，但是Master定理可以方便的判断出递归方程的解。产生这种结果的原因关键在于f(n)的形式，显然，当f(n)是n的多项式p(n)形式的话必然满足Master定理的要求，但是f(n)不是多项式就需要另当别论了。

下面就题目所列出的递归方程形式进行分析。

一、f(n)是n的多项式p(n)=f(n)

因为f(n)是多项式，设p(n)=O(n^k)，k≥0。根据递归树计算方式，有：

T(n)= aT(n/b)+n^k 。

T(n/b)= aT(n/b²)+(n/b)^k 。

T((n/b²)= aT(n/b³)+( n/b²)^k 。

……

于是得到：T(n)= n^k (1+ a/ b^k + (a/ b^k)² + (a/ b^k)³ +···+ (a/ b^k)^h)，h=log_bn。

1：log_ba=k

这种情况下a/ b^k= 1，显然T(n)= O(n^k log_bn)。

2：log_ba≠k

此时等比数列公比不是1，根据等比数列求和公式化简得到：

T(n)=( n^k –n^x)/(1-a/b^k)，x=log_ba。

如果log_ba，则T(n)= O(n^k)。

如果log_ba>k，则T(n)= O(n^x)。x=log_ba。

通过以上的计算表明，在Master定理的条件中，针对f(n)为多项式的情况可以使用递归树的方法进行证明和计算。同样，在f(n)不是多项式的时候也可以通过的这种方式得到方程的解。

二、f(n)是一般函数

当f(n)不是n的多项式的时候，计算就会变得比较复杂，有时可能会也找不到最终的解。但是递归树的方法给我们一种更好使用的解决办法。下面根据一个简单的例子说明这一点：

当a=b=2、f(n)=nlgn时候（lgn:log₂n的简记），计算递归方程的解。

T(n)= 2T(n/2)+nlgn 。

T(n/b)= 2T(n/2²)+(n/2)lg(n/2)。

T((n/b²)= 2T(n/2³)+ (n/2²)lg(n/2²)。

……

于是得到：T(n)= nlgn+(nlgn-lg2)+ (nlgn-2lg2)+ (nlgn-2²lg2)+···+(nlgn-2^hlg2)，h=lgn。

根据等差、等比数列求和公式化简有：

T(n)=n(lgn)² –(n-1)lg2，所以T(n)= O( n(lgn)²)，而不是O( nlgn)。

通过这个例子可以看出，当f(n)不是多项式的时候计算就有可能变得比较复杂，甚至无法计算。但是通过Master定理以及具体的数学变换技巧在某些情况下还是可行的。

综上所述，可以得出以下结论：在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里，使用递归树是一种比较可行的通用办法。

================================================================================

分析根据递归方程分析算法的时间复杂度时，常见到如下形式的方程，
T(n) = a * T(n/b) + f(n)
a ³ 1，b > 1，f(n)一般是个简单函数

这时可以有2种方法，来计算时间复杂度。一是用递归树，逐层代入原式，最终形成一个级数，
然后用一个函数来表达，得到T(n)。

二是应用主项定理Master Method 。其实，主项定理也就是对递归树方法的一种归纳，形成了
固定的计算方式，并分三种情形来计算。

这三种情形主要是比较 n^log_ba 与 f(n)，为什么要比较这两个函数呢？

观察原式，可以看出，n^log_ba其实相当于用递归树方法解出的递归方程的右侧的第一项，
而f(n)则是递归方程的右侧的第二项，这样，主项定理实际上是在比较组成结果的两个函数项，
而且这种比较是按照数量级（或者说是变化幅度）来比较的，也就是说，如2n 与 28n是
数量级（变化幅度）相当的。

这样就有了三种不同的情形：

1. f(n) < n^log_b^a

   也就是 f(n) = O(n^log_b^{a - e} ) ，e > 0为任意小的常数
   或者说，f(n) 比 n^log_ba变化的慢，慢n^e
   那么，T(n) Î Q (n^log_b^a)

2. f(n) > n^log_b^a

   也就是 f(n) = W(n^log_b^{a +e} ) ，e > 0为任意小的常数
   或者说，f(n) 比 n^log_ba变化的快，快n^e
   那么， T(n) Î Q(f(n))

   可以简单地说，递归方程的右侧的两项，哪项变化的块，T(n)就属于哪项的数量级

3. f(n) = n^log_b^a

   也就是两项的数量级相当，就给这个数量级乘上一个lg n
   
   T(n) Î Q(n^log_b^a * lg n)

主定理有三种情况，不同的情况有不同的用法
http://q0lc7q.bay.livefilestore.com/y1pSwpSxOEtVY-97QKYpa8oye8ErB74IdtNTDGcyurufgVYnHFX3TVK51aQOsGyQfRLTZZf5j9Tlcj2tbGVWHWN1xGsULMEHgd_/Mastermethod.PNG