这是CLRS手册中的一个问题。
算法研究小组网站介绍给出了以下答案：
（http://clrs.skanev.com/04/problems/03.html）
这个答案对吗我不明白最后两行。
最佳答案
不，不是。还有一个输入错误，而不是无穷大应该有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的θ当然，整个金额更大。