time - 解决重复: T(n)=2T(n/2)+n/logn

Question

我可以找到每行的总和(n/log n-i)，我也可以绘制它的递归树，但我无法计算它的行​​的总和。

T(n)=2T(n/2)+n/logn

T(1) = 1

Answer 1

假设 n = 2^k；

我们知道调和级数(欧拉公式):

Sum[i = 1 到 n](1/i) ~= log(n) [n -> 无穷大]

t(n) = 2t(n/2) + n/log(n)
     = 2(2t(n/4) + n/2/log(n/2)) + n/log(n)
     = 4t(n/4) + n/log(n/2) + n/log(n)
     = 4(2t(n/8) + n/4/log(n/4)) + n/log(n/2) + n/log(n)
     = 8t(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = 16t(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = n * t(1) + n/log(2) + n/log(4) + ... + n/log(n/2) + n/log(n)
     = n(1 + Sum[i = 1 to log(n)](1/log(2^i)))
     = n(1 + Sum[i = 1 to log(n)](1/i))
     ~= n(1 + log(log(n)))
     = n + n*log(log(n)))
     ~= n*log(log(n)) [n -> infinity]