第1个回答 2022-06-12
在阅读算法导论第四章的时候，求解一些递归式的复杂度时，遇到了一些问题，因此将思路分享一下。
首先对于可以用主方法求解的形式，这里不再说明，符合主方法的三种情况只要套用公式即可得到正确答案。关于主方法使用递归树法进行证明，算法导论上已经解释的很详细，感兴趣可以参考一下。
在练习题 4.6-2 中提到了 ， 其中 ，要求证明主递归式的的解为
以 为例，很明显不符合主方法的条件，因为第三章讲到过 ，那么可以考虑使用递归树法，进行求解，然后再使用代入法进行数学归纳法的证明。
首先递归树高度为 （书中 以2为底，而不是10），叶节点数量为 ，即数量为n，每个叶节点复杂度为 ，因此叶节点总的复杂度为
然后计算中间节点包括根节点的复杂度，每一层有 个子节点
接下来计算等差数列之和即可
即
总的复杂度
因此可以很清楚的看到，由于递归树的每层代价类似，最后结果多出来的 可以认为树的总层数进行累加的结果。
下面使用代入法验证该结论，由于证明渐近上界与证明渐近下界的过程类似，因此只证明上界。
设
则，
得证，其中
在思考题 4-3中 有类似 形式的递归式存在，其解为 ，有些解答认为是 实际上并不准确。
同样这种形式也不符合主方法的条件，同样使用递归树法进行近似的求解，然后再使用代入法证明答案的正确性。
在计算这个递归式需要使用一些调和级数的知识，在算法导论的附录A中有公式 A.7，调和级数求和的证明需要使用到积分的定理，这里就不赘述了。
同样，首先计算叶节点的复杂度，同上 叶节点数量为 ，即每个叶节点复杂度为 ，总的复杂度为
接下来计算中间节点包括根节点的复杂度，同上，一共有 层，各层之和为
这里的累加项不再是一个等比数列，而是一个调和级数，即为
所以可以看出进行多出一次对数运算的原因在于分数的累加，因此总的复杂度
同样，下面使用代入法证明结果的正确性，因为证明步骤类似，这里也只证明渐近上界为 , 设 ，所以有
下面证明 ，为了证明的简便，我们假设n为2的幂次，即 ，则
对于极限 ，那么有
于是，得证