526互联

递归式 T(n)=2T(n/2)+n/lgn的复杂度求解

发布时间 2023-04-26 20:49:59作者: ImreW

符合主递归式条件的情况

     首先对于可以用主方法求解的形式，这里不再说明，符合主方法的三种情况只要套用公式即可得到正确答案。

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

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

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

在计算这个递归式需要使用一些调和级数的知识

\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}}

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

\sum_{i=0}^{lgn-1} {\frac{1}{lgn - i}} = {\frac{1}{lgn}} + {\frac{1}{lgn -1 }} + ……+ {\frac{1}{2}} + 1 = ln(lgn) + O(1) = \theta (lglgn)

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

T(n) = g(n) + \theta (n) = n*\theta (lglgn) + \theta (n) = \theta (nlglgn)

同样，下面使用代入法证明结果的正确性，因为证明步骤类似，这里也只证明渐近上界为 O(nlglgn), 设T(n) \leq c*nlglgn，所以有

T(n) = 2T({\frac{n}{2}}) + {\frac{n}{lgn}} \leq 2*c*({\frac{n}{2}}lglg{\frac{n}{2}}) + {\frac{n}{lgn}} = cnlglg({\frac{n}{2}})+ {\frac{n}{lgn}}

下面证明 cnlglg({\frac{n}{2}})+ {\frac{n}{lgn}} \leq cnlglgn，为了证明的简便，我们假设n为2的幂次，即 2^k = n，则

cnlglg({\frac{n}{2}})+ {\frac{n}{lgn}} \leq cnlglgn

{\frac{n}{lgn}} \leq cn*(lglgn - lglg{{\frac{n}{2}}})

{\frac{1}{k}} <= c*(lg{{\frac{k}{k-1}}})

1 <= c*lg{(1+{\frac{1}{k-1}}})^k

对于极限 \lim\limits_{x \to \infty} {(1+\frac{1}{n})}^n = e，那么有

c*lg{(1+{\frac{1}{k-1}}})^k \geq c*lge\geq 1

于是，得证  T(n) \leq c*nlglgn