递归的复杂性T(n)=T(n−2)+1/lgn？

Question

这是CLRS书中的一个问题。算法研究小组网站的介绍给出了以下答案：

​

(http://clrs.skanev.com/04/problems/03.html)

这个答案对吗？我不明白最后两句话。

Answer 1

不，不是的。还有一个错误，而不是无穷大，应该有n。为了得到严格的数学证明，您应该在另一个stackExchange站点(数学站点)上询问。但由于你的直觉，我可以展示如下。

让我们想象一下，n = 2^2^k然后sum of 1/lg(i)等于

1/lg2 + 1/lg3 + 1/lg4 + 1/lg5 + 1/lg6 + 1/lg7 + 1/lg8 + 1/lg9 +
1/lg10 + 1/lg11 + 1/lg12 + 1/lg13 + 1/lg14 + 1/lg15 + ... + 1/lg n-1

这大约是

1/lg2 + 1/lg2 + 1/lg4 + 1/lg4 + 1/lg4 + 1/lg4 + 1/lg8 + 1/lg8 +
1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + ... + 1/lg n-1

等于

1/1 + 1/1 + 1/2 + 1/2 + 1/2 + 1/2 + 1/3 + 1/3 +
1/3 + 1/3 + 1/3 + 1/3 + 1/3 + 1/3 + ... + 1/ (2^k - 1) (as lg n = 2^k)

合并后我们有

sum(1/i * 2^i) from 1 to 2^k-1

最后一个成员是n/2 / 2^k-1，它是关于2^(2^k-k-1)的，这不是lg lg n = k的θ。当然，整笔金额甚至更大。