算法分析|集合4（解决重复）

在上一篇帖子中，我们讨论了 回路分析 .许多算法本质上是递归的。当我们分析它们时，我们得到了时间复杂度的递推关系。我们得到大小为n的输入上的运行时间作为n的函数，以及大小较小的输入上的运行时间。例如在 合并排序 ，要对给定数组进行排序，我们将其分成两半，然后递归地对两半重复该过程。最后我们合并结果。合并排序的时间复杂度可以写成T（n）=2T（n/2）+cn。还有很多其他算法，比如二进制搜索、河内塔等。

解决复发的方法主要有三种。

1） 替代法 ：我们猜测答案，然后用数学归纳法证明猜测是正确的还是错误的。

For example consider the recurrence T(n) = 2T(n/2) + nWe guess the solution as T(n) = O(nLogn). Now we use inductionto prove our guess.We need to prove that T(n) <= cnLogn. We can assume that it is truefor values smaller than n.T(n) = 2T(n/2) + n    <= 2cn/2Log(n/2) + n    =  cnLogn - cnLog2 + n    =  cnLogn - cn + n    <= cnLogn

2） 递归树方法： 在这种方法中，我们绘制一棵递归树，并计算每一层树所花费的时间。最后，我们总结了各个层面所做的工作。为了绘制递归树，我们从给定的递归开始，一直绘制，直到我们在级别之间找到一个模式。图案通常是算术或几何级数。

For example consider the recurrence relation T(n) = T(n/4) + T(n/2) + cn2           cn2         /           T(n/4)     T(n/2)If we further break down the expression T(n/4) and T(n/2), we get following recursion tree.                cn2           /                        c(n2)/16      c(n2)/4      /                /       T(n/16)     T(n/8)  T(n/8)    T(n/4) Breaking down further gives us following                 cn2            /                         c(n2)/16          c(n2)/4       /                  /      c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16 /          /        /           /      To know the value of T(n), we need to calculate sum of tree nodes level by level. If we sum the above tree level by level, we get the following seriesT(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....The above series is geometrical progression with ratio 5/16.To get an upper bound, we can sum the infinite series. We get the sum as (n2)/(1 - 5/16) which is O(n2)

3） 主方法： Master方法是获得解决方案的直接方法。主方法仅适用于以下类型的复发或可转换为以下类型的复发。

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

有以下三种情况： 1. 如果f（n）=O（n） ^C )其中c B 然后T（n）=Θ（n） ^{日志 _B A.} )

2. 如果f（n）=Θ（n） ^C )其中c=Log _B 然后T（n）=Θ（n） ^C 日志（n）

3. 如果f（n）=Ω（n） ^C )其中c>Log _B 然后T（n）=Θ（f（n））

这是怎么回事？ 主方法主要来源于递归树方法。如果我们画出T（n）=aT（n/b）+f（n）的递归树，我们可以看到在根上做的功是f（n），在所有叶子上做的功是Θ（n） ^c )其中c是Log _b a、 递归树的高度为对数 _B N

在递归树方法中，我们计算完成的总功。如果叶所做的功是多项式形式的，那么叶是主要部分，我们的结果就是叶所做的功（案例1）。如果叶和根的功是渐近相同的，那么我们的结果就是高度乘以任何水平的功（情况2）。如果根做的功是渐近更多的，那么我们的结果就是根做的功（情况3）。

一些标准算法的示例，这些算法的时间复杂度可以使用Master方法进行评估 合并排序 ：T（n）=2T（n/2）+Θ（n）。在情况2中，当c为1且对数为 _B a] 也是1。所以解决方案是Θ（n Logn）

二进制搜索 ：T（n）=T（n/2）+Θ（1）。在情况2中，它也会下降，因为c是0，并且是Log _B a也是0。因此，解决方案是Θ（Logn）

笔记： 1) T（n）=aT（n/b）+f（n）形式的递推不一定可以用主定理求解。给定的三个案例之间存在一些差距。例如，递归T（n）=2T（n/2）+n/Logn不能用主方法求解。

2) 情况2可以扩展为f（n）=Θ（n ^C 日志 ^K n） 如果f（n）=Θ（n） ^c 日志 ^K n） 对于某些常数k>=0和c=Log _B a、 那么T（n）=Θ（n） ^C 日志 ^k+1 n）

练习主定理的问题和解决方法。

接下来—— 算法分析|集5（摊销分析介绍）

参考资料： http://en.wikipedia.org/wiki/Master_theorem 麻省理工学院渐进记数法|重复|替换，主方法视频讲座 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论