首页 > 专题系列 > 算法分析 > 算法分析(2)-递归的时间复杂度
2014
03-13

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

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

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

T(n) = 2T(n/2) + cn. 还有许多其他算法,如二分查找,汉诺塔等都可以递推公式。

主要有三种方式来递归公式。

1)替代法:我们做一个猜测的解,然后用数学归纳法证明的猜测是正确的或不正确的。

例如:T(n) = 2T(n/2) + n。 我们猜测解为:T(n) = O(nLogn).

现在用数学归纳法来证明我们的猜测。

需要证明  T(n) <= cn Logn.  我们可以假设对于值小于n时这个公式是成立的。

T(n) = 2T(n/2) + n
    <= cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

2)递归树方法

在这个方法中,我们得出一个递归调用树,并计算树的每一层的时间。最后,我们对各层相加。要绘制递归树,我们从给定的递归出发,一直递推下去直到我们找到里面的模式。这个模式一般是典型的等差或等比级数。

例如对这个递归方程:T(n) = T(n/4) + T(n/2) + cn^2

           cn2     (cn2 即为 cn^2)
         /      \
     T(n/4)     T(n/2)

如果我们进一步分解表达T(n / 4)和T(n / 2),  我们得到以下递归树。

                cn2
           /           \      
       c(n2)/16      c(n2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 
           (一直向下分解cn2)
            /            \      
       c(n2)/16          c(n2)/4
       /      \            /      \
c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16
 /    \      /    \    /    \       /    \

要知道 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) ,所有的叶子节点的和为  \Theta \left(n^{{c}}\right) 其中 c为 \log _{b}a.

递归树的高度为:\log _{b}n

Master Theorem

在递归树的方法中,我们计算所有节点的和。如果在叶子节点的值是多项式的,那么叶子是占主导地位的一部分,而我们的结果变成叶子节点的值(情况1)。

如果叶和根是渐近一样的,那么结果就变成高度乘以在所有层的和(情况2)。如果根节点的值是渐近多,那么我们的结果变成在根的值(情况3)

一些时间复杂度可以使用主定理进行评估的例子

归并排序:为T(n) = 2T(n/2) + \Theta(n)它属于在第二种情况, c为1并且 \日志_ {B}一 也1。因此该解决方案是\西塔(nlogn)的

二分查找:T(n) = T(n/2) + \Theta(1). 。它也属于情况2.  c是0并且\日志_ {B}一也为0。因此该解决方案是\西塔(LOGN)

注:

1)主定理并不能用来解决所有形式为 T(n) = aT(n/b) + f(n) 的递归式,往往和给定的3种情况有第一定的差距。例如 T(n) = 2T(n/2) + n/Logn 不能用主定理解决。

2) 第二种情况可以扩展为 f(n) = \Theta \left(n^{{c}}\log ^{{k}}n\right).  如果 k >= 0 且 c = \log _{b}a, 那么 T(n) = \Theta \left(n^{{c}}\log ^{{k+1}}n\right)

更多问题及主定理解决方案

参考:http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/

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