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

永遇乐_2b88

简书作者

2019-10-22 20:19 IP属地: 上海

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

符合主递归式条件的情况

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

不符合主递归式条件乘以 $lgn$

在练习题 4.6-2 中提到了 $f(n)=θ((n^{log_b⁡a} ∗(lgn)^k )$ ，其中 $k \geq 0$ ，要求证明主递归式的的解为 $T(n) = \theta (n^{log_ba} lg^{k+1}n)$

以 $T(n) = 2T(n/2) + nlgn$ 为例，很明显不符合主方法的条件，因为第三章讲到过 $lg^bn = o(n^a)$ ，那么可以考虑使用递归树法，进行求解，然后再使用代入法进行数学归纳法的证明。

首先递归树高度为 $lgn$ （书中 $lg$ 以2为底，而不是10），叶节点数量为 $2^{lgn}$ ，即数量为n，每个叶节点复杂度为 $\theta (1)$ ，因此叶节点总的复杂度为 $\theta (n)$

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

$g(n) = \sum_{i=0}^{lgn-1} 2^i \bullet {\cfrac {n} {2^i}}\bullet lg({\cfrac {n} {2^i}})\ = n \bullet \sum_{i=0}^{lgn-1} (lgn - lg2^i) = n \bullet \sum_{i=0}^{lgn-1} (lgn - i) \leq nlgn \sum_{i=0}^{lgn-1}1 - n\sum_{i=0}^{lgn-1}i$

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

$\sum_{i=0}^{lgn-1}1 = lgn$

$\sum_{i=0}^{lgn-1} i= 0 + 1 + 2 +…+ lgn -1 = {\frac{lgn\bullet (lgn-1)}{2}}$

即 $g(n) = nlg^2n - {\frac{nlgn(lgn-1)}{2}} = \theta (nlg^2n)$

总的复杂度 $T(n) = g(n) + \theta (n) = \theta (nlg^2n) + \theta (n) = \theta (nlg^2n)$

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

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

设 $T(n) \leq cnlg^2n$

则， $T(n) = 2T(n/2) + nlgn \leq 2 * c * {\frac{n}{2}}*lg^2{{\frac{n}{2}}} + nlgn = cn*(lgn-1)^2 + nlgn$

$= cn*(lg^2n -2lgn +1) + nlgn = cnlg^2n - ((2c-1)nlgn-cn) \leq cnlg^2n$

得证，其中 $c>{\frac{1}{2}}$

不符合主递归式条件除以 $lgn$

在思考题 4-3中有类似 $T(n) = 2T({\frac{n}{2}}) + {\frac{n}{lgn}}$ 形式的递归式存在，其解为 $\theta(nlglgn)$ ，有些解答认为是 $\theta(nlgn)$ 实际上并不准确。

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

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

$\sum_{k=1}^{n}{\frac{1}{k}} = lnn +O(1)$

同样，首先计算叶节点的复杂度，同上叶节点数量为 $2^{lgn} = n$ ，即每个叶节点复杂度为 $\theta (1)$ ，总的复杂度为 $\theta (n)$

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

$g(n) = \sum_{i=0}^{lgn-1} 2^i * ({\frac{{\frac{n}{2^i}}}{lg{{\frac{n}{2^i}}}}}) = n*\sum_{i=0}^{lgn-1} {\frac{1}{lgn - lg2^i}} = n*\sum_{i=0}^{lgn-1} {\frac{1}{lgn - i}}$