Question

算法导论 4-3 递归式 T(n)=2T(n/2)+n/lgn的复杂度求解

Answer 1

     在阅读算法导论第四章的时候，求解一些递归式的复杂度时，遇到了一些问题，因此将思路分享一下。

     首先对于可以用主方法求解的形式，这里不再说明，符合主方法的三种情况只要套用公式即可得到正确答案。关于主方法使用递归树法进行证明，算法导论上已经解释的很详细，感兴趣可以参考一下。

    在练习题 4.6-2 中提到了    ， 其中   ，要求证明主递归式的的解为  

    以   为例，很明显不符合主方法的条件，因为第三章讲到过  ，那么可以考虑使用递归树法，进行求解，然后再使用代入法进行数学归纳法的证明。

    首先递归树高度为  （书中  以2为底，而不是10），叶节点数量为  ，即数量为n，每个叶节点复杂度为  ，因此叶节点总的复杂度为 

    然后计算中间节点包括根节点的复杂度，每一层有   个子节点

    

    接下来计算等差数列之和即可

              

        

即   

总的复杂度 

     因此可以很清楚的看到，由于递归树的每层代价类似，最后结果多出来的   可以认为树的总层数进行累加的结果。

    下面使用代入法验证该结论，由于证明渐近上界与证明渐近下界的过程类似，因此只证明上界。

    设 

    则，

得证，其中 

    在思考题 4-3中 有类似   形式的递归式存在，其解为  ，有些解答认为是   实际上并不准确。

    同样这种形式也不符合主方法的条件，同样使用递归树法进行近似的求解，然后再使用代入法证明答案的正确性。

    在计算这个递归式需要使用一些调和级数的知识，在算法导论的附录A中有公式 A.7，调和级数求和的证明需要使用到积分的定理，这里就不赘述了。

    同样，首先计算叶节点的复杂度，同上 叶节点数量为  ，即每个叶节点复杂度为  ，总的复杂度为 

    接下来计算中间节点包括根节点的复杂度，同上，一共有  层，各层之和为

        

这里的累加项不再是一个等比数列，而是一个调和级数，即为

所以可以看出进行多出一次对数运算的原因在于分数的累加，因此总的复杂度 

同样，下面使用代入法证明结果的正确性，因为证明步骤类似，这里也只证明渐近上界为  , 设 ，所以有

下面证明  ，为了证明的简便，我们假设n为2的幂次，即  ，则

对于极限  ，那么有

于是，得证