　开篇前言：为什么写这篇文章？笔者目前在学习各种各样的算法，在这个过程中，频繁地碰到到递归思想和分治思想，惊讶于这两种的思想的伟大与奇妙的同时，经常要面对的一个问题就是，对于一个给定的递归算法或者用分治思想缩小问题规模的算法，如何求解这个算法的时间复杂度呢？在google过很多的博文后，感觉这些博文总结的方法，有很好优秀的地方，但是都不够全面，有感于此，笔者决定总结各家之长，作此博文，总结各种方法于此，有不足之处，欢迎各位批评指证！

　　在算法的分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化成为一个递归方程的求解。而对递归方程的求解，方法多种多样，不一而足。本文主要介绍目前主流的方法：代入法，迭代法，公式法，母函数法，差分方程法。

　　【代入法】代入法首先要对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。

　　【举例】我们有如下的递归问题：T(n)=4T(n/2)+O(n)，我们首先预测时间复杂度为O(n²),不妨设T(n)=kn²（其中k为常数），将该结果带入方程中可得：左=kn²，右=4k(n/2)²+O(n)=kn²+O(n),由于n²的阶高于n的阶，因而左右两边是相等的，接下来用数学归纳法进行验证即可。

　　【迭代法】迭代法就是迭代的展开方程的右边，直到没有可以迭代的项为止，这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解，为方便讨论起见，给出其递归方程的一般形式：

　　【举例】下面我们以一个简单的例子来说明：T(n)=2T(n/2)+n²,迭代过程如下：

　　容易知道，直到n/2^(i+1)=1时，递归过程结束，这时我们计算如下：

　　到这里我们知道该算法的时间复杂度为O(n²)，上面的计算中，我们可以直接使用无穷等比数列的公式，不用考虑项数i的约束，实际上这两种方法计算的结果是完全等价的，有兴趣的同学可以自行验证。

　　【公式法】这个方法针对形如：T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子问题的解的综合，得到原问题的解。这种方法是对于分治问题最好的解法，我们先给出如下的公式：

　　公式记忆：我们实际上是比较n^log_ba和f(n)的阶，如果他们不等，那么T(n)取他们中的较大者，如果他们的阶相等，那么我们就将他们的任意一个乘以logn就可以了。按照这个公式，我们可以计算【迭代法】中提到的例子：O(f(n))=O(n²),容易计算另外一个的阶是O(n),他们不等，所以取较大的阶O(n²)。太简单了，不是吗？

　　需要注意：上面的公式并不包含所有的情况，比如第一种和第二种情况之间并不包含下面这种情况：f(n)是小于前者，但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下，笔者将公式表述成如上的情况，但是并不是很严谨，关于该公式的严密讨论，请看这里。但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。

　　特别地，对于我们经常碰到的，当f(n)=0时，我们有：

　　【母函数法】母函数是用于对应于一个无穷序列的幂级数。这里我们解决的递归问题是形如：T(n)=c₁T(n-1)+c₂T(n-2)+c₃T(n-3)+...+c_kT(n-k)+f(n)。为说明问题简便起见，我们选择斐波那契数列的时间复杂度作为例子进行讨论。

　　【举例】斐波那契数列递归公式：T(n)=T(n-1)+T(n-2)。这里我们假设F(n)为第n项的运算量。则容易得到：F(n)=F(n-1)+F(n-2),其中F(1)=F(2)=1.我们构造如下的母函数：G(x)=F(1)x+F(2)x²+F(3)x³+......,我们可以推导如下：

　　上面的方法计算相对来说是比较简单的，关键在于对于母函数的理解，刚开始的时候可能不是很好理解，对于母函数可以参考这里和维基百科这里。

　　【差分方程法】可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。这里我们只考虑最长常见的递归形式，形如：T(n)=c₁T(n-1)+c₂T(n-2)+c₃T(n-3)+...+c_kT(n-k)+f(n)，其中c1,c2,...ck为常数且不等于0；我们对该方程的求解如下：