[理工] 演算法

[kobebset105 (小小小妹)]

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
推 can18: 第6題 他是問已知2個subproblem的解，combine要花多少時間
→ can18: T(n) = 2T(n/2) + f(n)
→ can18: abc分別給不同的 f(n)值，求整個T(n)的複雜度
推 can18: 答案應該是 a.O(NlgN) b.O(N lg^2 N) c. O(N^2)
推 can18: 然後第五題2我不確定 但3.fibnacci heap沒記錯的話是O(VlgV
→ can18: +E) 所以答案應該是O(E) 或O(V^1.5)
→ kobebset105: 謝大大