Cormen ch4-4 b
T(n) = 5T(n/5) + n/lg n
我的解法:
T(n) = 5T(n/5) + n/lg n
= 25T(n/25) + 5*(n/5)/lg (n/5) + n/lg n
i=lg n
=5^i*T(n/5^i) + Σ [ n/(lg n -ilg 5)]
i=0
令n/5^i = 1 得 i=lg n (以5为底)
接下来不会处理后面的sigma了，求解
答案是 θ(n lglg n)

答案是O(nloglogn)吧1/1+1/2+1/3+...+1/n=1/(log n)

还是不懂s大的意思

了解，谢谢s大