[理工] 演算法 時間複雜度

[suspect1 ()]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1514960463.A.91B.html
推 s1020824: 答案是O(nloglogn)吧
→ s1020824: 1/1+1/2+1/3+...+1/n=1/(log n)
 已更正
※ 編輯: suspect1 (42.72.131.9), 01/03/2018 14:33:37
→ suspect1: 還是不懂s大的意思
→ s1020824: http://i.imgur.com/86M4yjW.jpg
→ suspect1: 瞭解，謝謝s大