这是 CLRS 书中的一道题。 Introduction to Algorithms Study Group网站对此给出了如下回答:
( 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)
的,这远不是 theta lg lg n = k
。当然,总和甚至更大。
关于algorithm - 递归的复杂度 T(n)=T(n−2)+1/lgn?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32742573/