这个方法为估计形如：

　　T(n) = aT(n/b) + f(n)

　　其中，a≥1和b≥1，均为常数，f(n)是一个确定的正函数。在f(n)的三类情况下，我们有T(n)的渐近估计式：

    1.若对于某常数ε>0，有f(n) = O(nlogb a-ε )，则T(n) = O(nlogb a )
    
    2.若f(n) = O(nlogb a )，则T(n) = O(nlogb a *logn)
    
    3.若f(n) = O(nlogb a+ε )，且对于某常数c>1和所有充分大的正整数n，有af(n/b)≤cf(n)，则T(n)=O(f(n))。
    
    设T(n) = 4T(n/2) + n，则a = 4，b = 2，f(n) = n，计算得出nlogb a = nlog2 4 = n2 ，而f(n) = n = O(n2-ε )，此时ε= 1，根据第1种情况，我们得到T(n) = O(n2 )。
    
    这里涉及的三类情况，都是拿f(n)与nlogb a 作比较，而递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数nlogb a 较大，则T(n)=O(nlogb a )；在第三类情况下，函数f(n)较大，则T(n)=O(f (n))；在第二类情况下，两个函数一样大，则T(n)=O(nlogb a *logn)，即以n的对数作为因子乘上f(n)与T(n)的同阶。

一．前言

   递归函数的主要思想是将一个问题分拆为几个子问题（问题大小减少），分别解决这些子问题，再将得到的结果组合起来。所以，递归函数的复杂度包括分拆问题的代价，组合结果的代价（统称称为非递归代价）和解决子问题的代价（递归复杂度）。

   递归函数的复杂度分析主要是通过递归方程和递归树进行分析的。首先，将一个递归函数的复杂度表示成递归方程的形式，然后通过数学计算或递归树分析，得到递归函数的近似复杂度。这里主要介绍两种递归函数的复杂度分析方法。（这里主要指时间复杂度）

1．Divide-and-Conquer(分而治之)

这种类型的递归函数的复杂度可以用递归方程表示为

   T(n)=bT(n/c)+f(n)                ------------------------(1)

显而易见，这种方法是将一个问题分拆为几个问题大小相同的子问题。f(n)叫非递归代价，主要是指分拆问题和组合结果的代价

2．Chip and Conquer

这种类型的递归函数的复杂度可以用递归方程表示为

   T(n)=T(n-c)+f(n)                 ------------------------(2)

或更一般地，

   T(n)=bT(n-c)+f(n)                ------------------------(3)

   显然，这种方法是将问题大小逐步减小，一直减小到可以解决的问题大小（也就是base-case）.

二．递归树

下面介绍分析复杂度的一个重要工具-----递归树

    递归树的结点有两个域，如下图：

     根结点的每个子结点都代表了这个问题分拆的一个子问题的复杂度。就这样递归地分解问题。一直到达叶子结点，也就是base-case.在前面的讨论中，我们没有涉及base-case，在使用递归树分析复杂度时，我们假设base-case的复杂度为1。

     举一个例子就可以很明白的说明如何构造递归树。

Example1:     由递归方程T(n)=2T(n/2)+n构造递归树

     首先，构造根接点

它的子结点是

     ……,以此类推。所以，最后的递归树为：

  递归树规则:

     根结点的复杂度=所有非叶结点的非递归复杂度+叶子结点的复杂度。

所以，在上面的例子中，每层的非递归复杂度为n,而base-case出现在大约lgn层(n/2^d =1;d = lgn)。由于base-case的复杂度为1，所以T(n)≈nlgn，即

     递归树是分析和计算递归方程的一个重要工具。它可以直观地表示出递归函数的复杂度，并使人易于理解。

三．Divide-and-Conquer问题的解决方案

     在上面的例子中，我们用递归树规则得出了递归函数大概的时间复杂度。但递归树只能粗略地解决一小部分问题。这里要介绍Divide-and-Conquer类问题更一般的解决方案—Master定理。

     不过为了更好的理解和使用Master定理，我们先要进一步地分析一下递归树，并介绍一个重要的参数：关键幂

     回忆一下递归方程（1）的递归树。

每增加一层，函数的问题大小就减少c倍。假设base-case出现在第D层，则n/c^D=1; D=㏒c(n).使用换底公式，D=lg(n)/lg(c).

而同时每增加一层，这层的结点个数就增加b倍。所以第D层的结点个数为L=b^D(L表示D层的结点个数)。两边取对数，得lg(L)=Dlg(b);将D=lg(n)/lg(c)带入上式，得lg(L)=(lg(b)/lg(c))lg(n).这时lg(n)前面的系数就被叫做关键幂。一般用E来表示。

所以E=lg(b)/lg(c),而lg(L)=Elg(n),从而我们可以看出L=n^E。

下面就是著名的Master定理：

这个方法为估计形如：

　　T(n) = aT(n/b) + f(n)

　　其中，a≥1和b≥1，均为常数，f(n)是一个确定的正函数。在f(n)的三类情况下，我们有T(n)的渐近估计式：

    1.若对于某常数ε>0，有f(n) = O(n^log_ba-ε)，则T(n) = O(n^log_ba)
    
    2.若f(n) = O(n^log_ba)，则T(n) = O(n^log_ba*logn)
    
    3.若f(n) = O(n^log_ba+ε)，且对于某常数c>1和所有充分大的正整数n，有af(n/b)≤cf(n)，则T(n)=O(f(n))。
    
    设T(n) = 4T(n/2) + n，则a = 4，b = 2，f(n) = n，计算得出n^log_ba = n^log₂4 = n²，而f(n) = n = O(n^2-ε)，此时ε= 1，根据第1种情况，我们得到T(n) = O(n²)。
    
    这里涉及的三类情况，都是拿f(n)与n^log_ba作比较，而递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数n^log_ba较大，则T(n)=O(n^log_ba)；在第三类情况下，函数f(n)较大，则T(n)=O(f (n))；在第二类情况下，两个函数一样大，则T(n)=O(n^log_ba*logn)，即以n的对数作为因子乘上f(n)与T(n)的同阶。
    

在解决递归函数的复杂度方面十分简单，方便。但理解Master定理比较难，可以利用递归树进行理解。而且Master定理的证明也较复杂，故这里不列出。

四．Chip-and-Conquer问题的解决方案

    我们先考虑Chip-and_Conquer问题的一般情况，递归方程（3）

T(n)=bT(n-c)+f(n)

同样，我们使用递归树进行分析，递归树和Divide-and-Conquer类问题的递归树基本一样，这里就不再重复。只是对递归树进行一下分析。

显然，base-case出现在n/c层，而且第n/c层的每个结点代价为1（假设）

首先，计算一下各层所有结点的非递归代价,第 i 层的所有结点的非递归代价是(b^i)*f(n-ic).

 所以，根结点的复杂度（也就是递归函数的复杂度）为

 T(n)=∑0…n/c (b^i)*f(n-ic).     令h=(n/c)-i，得

 T(n)=b^(n/c)∑0…n/c f(ch)/b^h ∈⊙(b^(n/c));

所以，这种递归函数的复杂度是随指数增长的，显然，指数增长的算法不具有任何意义。这种问题的递归方法是不实用的。

不过，考虑到它一种特别情况：就是递归方程（2）

    T(n)=T(n-c)+f(n)

即b=1的情况。

这时，复杂度

T(n)= ∑0…n/c f(n-ic) =∑0…n/c f(ch) ≈(1/c)∫0…nf(x)dx(定积分的定义)

此时,若f(n) ∈⊙(n^a),则T(n) ∈⊙(n^(a+1));

若f(n) ∈⊙(logn),则T(n) ∈⊙(nlogn);这样的复杂度是可以接受的。

五．小结

     总之，在计算和分析递归函数的复杂度时，我们主要会使用递归方程和递归树这两种工具。尤其是递归树，可以应用在更多的情况下，来解决递归函数复杂度的问题。对于Divide-and-Conquer类问题，还有一个很方便的定理：Master定理。这个定理在使用中是非常方便的，但它有它的局限性，故有Master定理的扩展定理，不过篇幅所限，这里不再介绍。