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

看板Grad-ProbAsk作者時間8年前 (2018/01/03 14:21), 8年前編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 8年前最新討論串2/7 (看更多)
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
推
01/03 14:28, 8年前 , 1F
答案是O(nloglogn)吧
01/03 14:28, 1F
→
01/03 14:29, 8年前 , 2F
1/1+1/2+1/3+...+1/n=1/(log n)
01/03 14:29, 2F
已更正 ※ 編輯: suspect1 (42.72.131.9), 01/03/2018 14:33:37
→
01/03 14:36, 8年前 , 3F
還是不懂s大的意思
01/03 14:36, 3F
→
01/03 14:45, 8年前 , 4F
01/03 14:45, 4F
→
01/03 14:53, 8年前 , 5F
瞭解，謝謝s大
01/03 14:53, 5F
‣ 更多 suspect1 的文章
文章代碼(AID): #1QJ7PFaR (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 7 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共7篇)
‣ 更多 suspect1 的文章
文章代碼(AID): #1QJ7PFaR (Grad-ProbAsk)