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

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

【代入法】代入法首先要对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。
【举 例】我们有如下的递归问题：T(n)=4T(n/2)+O(n)，我们首先预测时间复杂度为O(n2),不妨设T(n)=kn2（其中k为常数），将该结果带入方程中可得：左=kn2，右=4k(n/2)2+O(n)=kn2+O(n),由于n2的阶高于n的阶，因而左右两边是相等的，接下来用数学归纳法进行验证即可。

数学归纳法相信大家都知道，是一个完全正确的演绎推理方法，不清楚的可以百度下。

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

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

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

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

其实迭代法，最直观的还是借助树形结构，把公式按树形分解，很容易就可以得出结论，并且分解为树也是证明公式法的一个很好的方法，因为我们很容易就知道树的高以及叶子节点的数目，比如：T(n)=aT(n/b)+f(n),我们很容易就知道高度h = logb(n).因为最终会将T（n/b^h)）分解到T（1）,所以
n/b^h=1=>h=logb(n). 也很容易知道叶子节点数为a^h=a^(logb(n))=n^logb(a);

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

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

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

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

剩下的方法请参考：https://www.cnblogs.com/lixuwu/p/5676161.html#_label0