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

符合主递归式条件的情况

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

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

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

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

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

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

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

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

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

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

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

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

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

对于极限 那么囿