作者suspect1 ()
看板Grad-ProbAsk
标题[理工] 演算法 时间复杂度
时间Wed Jan 3 14:21:00 2018
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)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.131.9
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1514960463.A.91B.html
1F：推 s1020824: 答案是O(nloglogn)吧 01/03 14:28
2F：→ s1020824: 1/1+1/2+1/3+...+1/n=1/(log n) 01/03 14:29
已更正
※ 编辑: suspect1 (42.72.131.9), 01/03/2018 14:33:37
3F：→ suspect1: 还是不懂s大的意思 01/03 14:36
5F：→ suspect1: 了解，谢谢s大 01/03 14:53