算法|集4的分析(解递归)- GeeksforGeeks188金宝搏滚球投注

|算法集4的分析(递归求解)

难度等级:媒介
最后更新:2020年4月22日,

在之前的文章中，我们讨论了分析循环。许多算法本质上是递归的。当我们分析它们时，我们得到了时间复杂度的递推关系。我们得到了规模为n的输入的运行时间是n的函数，以及规模较小输入的运行时间。例如在归并排序，为了对给定的数组排序，我们将它分成两部分，然后递归地对这两部分重复此过程。最后我们合并结果。归并排序的时间复杂度可以写成T(n) = 2T(n/2) + cn。还有许多其他算法，如二叉搜索，河内塔等。

解递归式主要有三种方法。

1)替换法:我们对答案进行猜测，然后用数学归纳法来证明猜测是对还是错。

例如，考虑递归式T(n) = 2T(n/2) + n，我们猜解为T(n) = O(nLogn)。现在我们用归纳法来证明猜想。我们需要证明T(n) <= cnLogn。我们可以假设小于n的值是正确的。T(n) = 2T(n/2) + n <= 2cn/2Log(n/2) + n = cnLogn - cnLog2 + n = cnLogn - cn + n <= cnLogn

2)递归树法:在这种方法中，我们画一个递归树，并计算树的每一层所花费的时间。最后，我们总结了在各级所做的工作。为了画递归树，我们从已知的递归开始，一直画，直到我们在层间找到一个模式。该模式通常是算术或几何级数。

例如，考虑递归关系T(n) = T(n/4) + T(n/2) + cn²cn²如果我们进一步分解表达式T(n/4)和T(n/2)，我们得到以下递归树。cn²/ \ c (n²) / 16 c (n²/4 / \ / \ T(n/16) T(n/8) T(n/8) T(n/4)进一步细分，我们得到以下cn²/ \ c (n²) / 16 c (n²)/4 / \ / \ c(n .²) / 256 c (n²) / 64 c (n²) / 64 c (n²)/16 / \ / \ / \ / \要知道T(n)的值，我们需要逐级计算树节点的和。如果我们逐层求和，我们得到下面的级数T(n) = c(n²+ 5(n²)/16 + 25(n²)/256)+ ....以上级数为比值为5/16的几何级数。为了得到上界，我们可以对无穷级数求和。和是(n²/(1 - 5/16)也就是O(n²)

3)掌握方法:
主方法是一种直接求得解的方法。主方法仅对下列类型的递归或可转换为下列类型的递归有效。

T(n) = aT(n/b) + f(n)其中a >= 1, b > 1

有以下三种情况:
1.如果f(n) = Θ(n^c)，其中c < Log . Log_ba then T(n) = Θ(n^{日志_b一个})

2.如果f(n) = Θ(n^c)，其中c = Log_ba then T(n) = Θ(n^co (Log n))

3.如果f(n) = Θ(n^c)，其中c > Log_ba then T(n) = Θ(f(n))

这是如何工作的呢?
主方法主要由递归树法推导而来。如果我们画出T(n) = aT(n/b) + f(n)的递归树，我们可以看到根结点所做的功是f(n)，所有叶结点所做的功是Θ(n)^c)，其中c为Log_ba.递归树的高度为Log_bn
主定理
在递归树法中，我们计算所做的总功。如果工作在叶子多项式,然后叶子是占主导地位的一部分,我们的结果成为了工作在叶子(情况1)。如果工作在叶子和根是一样渐近,那么结果就变得高度乘以各级工作(例2)。如果工作根多是渐近,那么我们的结果就变成了在根(情况3)处做的功。