[理工] 演算法

看板Grad-ProbAsk作者 (小小小妹)時間6年前 (2017/11/16 16:32), 6年前編輯推噓3(304)
留言7則, 2人參與, 6年前最新討論串7/11 (看更多)
https://i.imgur.com/0YLEDOu.jpg
第五題的二跟三是O(VlogV)嗎 我沒解答我想確認一下 還有第六題divide and conquer 子問題的複雜度跟整個問題的複雜度不是一樣嗎 還是我誤會了 第六題不知如何開始 請教各位大大了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.9.27 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510821148.A.154.html ※ 編輯: kobebset105 (1.161.9.27), 11/16/2017 16:32:59

11/16 21:51, 6年前 , 1F
第6題 他是問已知2個subproblem的解,combine要花多少時間
11/16 21:51, 1F

11/16 21:52, 6年前 , 2F
T(n) = 2T(n/2) + f(n)
11/16 21:52, 2F

11/16 21:53, 6年前 , 3F
abc分別給不同的 f(n)值,求整個T(n)的複雜度
11/16 21:53, 3F

11/16 21:55, 6年前 , 4F
答案應該是 a.O(NlgN) b.O(N lg^2 N) c. O(N^2)
11/16 21:55, 4F

11/16 21:58, 6年前 , 5F
然後第五題2我不確定 但3.fibnacci heap沒記錯的話是O(VlgV
11/16 21:58, 5F

11/16 21:58, 6年前 , 6F
+E) 所以答案應該是O(E) 或O(V^1.5)
11/16 21:58, 6F

11/16 23:58, 6年前 , 7F
謝大大
11/16 23:58, 7F
文章代碼(AID): #1Q3KqS5K (Grad-ProbAsk)
討論串 (同標題文章)
文章代碼(AID): #1Q3KqS5K (Grad-ProbAsk)