前面的文章讨论了循环的时间复杂度分析。 许多算法具有递归性质，我们分析时得到的是递归关系的时间复杂度。
例如，在合并排序中，对给定数组进行排序，将其分成两半，然后对这一半递归重复该过程。 最后，我们将合并结果。 时间的复杂性可以写成如下
t(n )=2t ) n/2 ) cn .其他的二分搜索、汉诺威等很多算法都是递归式的。
递归公式主要有三种方法。
1 )替代法：建立推测的解，用数学归纳法证明的推测是正确的还是不正确的。
例如，t(n )=2t ) n/2 ) n。 我们推测是t(n )=o ) (nlogn )。
现在用数学归纳法证明我们的推测。
必须证明t(n )=cn Logn。 如果值小于n，则可以假设这个公式成立。
1
t(n )=2t ) n/2 ) n
2
=cn/2log(n/2 ) n
3
=cnLogn - cnLog2 n
4
=cnLogn - cn n
5
=cnLogn
2 )递归树的制作方法
该方法得到递归调用树，并计算树每层的时间。 最后，我们把每一层相加。 要画递归树，从给定的递归出发，递归地去，直到找到里面的模式。 这个模式一般是典型的等差或等比级数。
例如，对于递归方程，t(n )=t ) n/4 ) t ) n/2 ) cn^2
1
cn2(cn2为cn^2)
2
//
3
t(n/4 ) t ) n/2 ) )。
再将t(n/4 )和t(n/4 )分解表示，可以得到以下递归树。
01
cn2
02
//
03
C(N2 )/16C ) N2 )/4
04
//
05
t(n/16 ) t ) n/8 ) t ) n/8 ) t ) n/4 ) ) )
06
(将cn2一直向下分解)
07
//
08
C(N2 )/16C ) N2 )/4
09
//
10
c(N2 )/256c ) N2 )/64c )/64c ) N2 )/16
11
(() () )/) ) )。
要知道T(N )的值，必须将所有图层的值相加。 从最上面开始相加，可以得到以下公式。
t(n )=c(n^25(n^2)/1625 ) n^2)/256 ) .
上述系列几何级数为5/16。
为了得到一个上限，求无穷级数之和。 (n^2)/) 15/16是o ) n^2)
定理
主定理是解决递归的直接方法。 但是，它仅用于可以转换为几种类型或以下类型的递归表达式中：
t(n )=at(n/b ) f ) n ) (a=1且b 1 ) ) ) ) ) ) ) ) t(n )=at(n/b ) f )
存在以下三种情况：
怎么计算？
主定理主要来源于递归树的方法。 当绘制t(n )递归树t(n )=at(n/b ) f ) n )时，根节点的值为f(n )，所有叶节点之和为
但是，c是
水平。
递归树的高度如下。
递归树方法计算所有节点的和。 如果叶的节点的值是多项式的话，叶是支配性的部分，我们的结果就是叶的节点的值(情况1 )。
如果叶和根是渐近的，则结果是所有层中的和与高度相乘(情况2 )。 根节点的值渐进地多的话，我们的结果就是根中的值(情况3 )
也有可以使用主定理评价时间复杂性的例子
合并排序： t(n )=2t (n/2 )。 这是第二种情况，c是1
也是1。 因此，该解决方案
二分搜索： t(n ) t(n ) n/2 ) ) ) ) ) )二分搜索： t(n )=t (n/2 ) ) ) ) ) ) )二分搜索) )二分搜索)二分搜索) ) ) ) 652 )
.的。 这也是情况2. c为0
也变成0。 因此，该解决方案
注：
1 )主定理并不是所有的形式都用来解决t(n )=at ) n/b ) f ) n )的递推公式，往往与给定的三种情况有第一定的差别。 例如，t(n )=2t ) n/2 ) n/Logn不能用主定理解决。
2 )第二种情况可以扩展到f(n )=
. k=0且c=的情况
，t(n )=
更多问题和主定理解决方案
参考： http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrence s /
参考视频地址： http://v.163.com/movie/2010/12/2/e/M6 utt 5u 0i _ M6 v2t 4t 2e.html
原文： http://www.acme rblog.com/analysis-recurrence s-5084.html