算法分析(2)-递归的时间复杂度

在前面的文章中，我们讨论了循环的时间复杂度分析。很多算法是具有递归性质的，当我们的分析的时候得到的是递推关系的时间复杂度。

例如，在归并排序中，对一个给定的数组进行排序，我们把它分成两半，并对这两半递归地重复这个过程。最后，我们合并结果。时间复杂度可以写成：

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 / 2), 　我们得到以下递归树。

01

cn2

02	/           \

03	c(n2)/16      c(n2)/4

04	/      \          /     \

05	T(n/16)     T(n/8)  T(n/8)    T(n/4)

06	(一直向下分解cn2)

07	/            \

08	c(n2)/16          c(n2)/4

09	/      \            /      \

10	c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16

11	/    \      /    \    /    \       /    \

要知道 T(n)的值，我们需要相加所有层的值。如果从最上面开始加，可以得到下面的式子：

T(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….

上述系列是几何级数为5/16。

为得到一个上限,我们求无穷级数的和： (n^2)/(1 – 5/16) 即为 O(n^2)

主定理

主定理是解决递归的一种直接方法。但仅用于一些类型或可以转换为以下类型的递归公式：

T(n) = aT(n/b) + f(n)  （a >= 1 且 b > 1）

有以下三种情况：

如何计算？

主定理主要来自递归树方法。如果我们画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/2) + . 。它也属于情况2.  c是0并且也为0。因此该解决方案是

注：

1）主定理并不能用来解决所有形式为 T(n) = aT(n/b) + f(n) 的递归式，往往和给定的3种情况有第一定的差距。例如 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-recurrences/

参考视频地址：http://v.163.com/movie/2010/12/2/E/M6UTT5U0I_M6V2T4T2E.html

原文：http://www.acmerblog.com/analysis-recurrences-5084.html