Re: [理工] 104台大資演 Prim's

看板Grad-ProbAsk作者 (levi)時間7年前 (2019/01/07 20:23), 編輯推噓3(3推 0噓 4→)
留言7則, 3人參與, 7年前最新討論串2/2 (看更多)
不好意思，這篇藉著前人的文來問第二小題，第二小題我看網友的答案是O(V^2)，但我自 己後來推了幾次，到現在還是覺得Loser Tree可以用來當Priority Queue(V個Run，E個Da ta，建樹：O(V)，找最小找到結束：O(ElogV)) 這個樣子的話Extract-min(Q)就可以由一般的搜尋V*V降到V*logV，DcreaseKey總共則是E logV(如果演算中不用任何DecreaseKey，我認為是O((V-1)*2E)=O(VE)，意即每次跑新的 點要更新cost陣列時都要全部2E條邊跑一遍) 以上是小弟想法，還請教各位演算神人的指導，感謝！ ※ 引述《cschenptt (chen)》之銘言： : 題目： : https://i.imgur.com/jZlEzBr.png
: 我的想法： : https://i.imgur.com/JDGuqyF.jpg
: 謝謝大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.199.196 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546863801.A.682.html
推
01/08 19:08, 7年前 , 1F
1. E=O(V^1.5) => O(V^2.5) ?
01/08 19:08, 1F
推
01/08 19:11, 7年前 , 2F
2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV)
01/08 19:11, 2F
→
01/08 19:11, 7年前 , 3F
我的想法也是這樣
01/08 19:11, 3F
→
01/08 23:41, 7年前 , 4F
第一題因為 findmin 是 O(n), decreasekey 是 O(1)
01/08 23:41, 4F
→
01/08 23:42, 7年前 , 5F
所以複雜度應該是 O(|V|*n + |E| * 1) = O(nV) = (V^2)
01/08 23:42, 5F
推
01/09 09:48, 7年前 , 6F
Decrease Key 用Fib.heap才是O(1)?
01/09 09:48, 6F
→
01/10 20:28, 7年前 , 7F
Array decrease key 也是O(1)
01/10 20:28, 7F
‣ 更多 leviliang 的文章
文章代碼(AID): #1SCqIvQ2 (Grad-ProbAsk)
‣ 更多 leviliang 的文章
文章代碼(AID): #1SCqIvQ2 (Grad-ProbAsk)