作者leviliang (levi)
看板Grad-ProbAsk
標題Re: [理工] 104台大資演 Prim's
時間Mon Jan 7 20:23:18 2019
不好意思，這篇藉著前人的文來問第二小題，第二小題我看網友的答案是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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1546863801.A.682.html
1F：推 htc018220: 1. E=O(V^1.5) => O(V^2.5) ? 01/08 19:08
2F：推 htc018220: 2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV) 01/08 19:11
3F：→ htc018220: 我的想法也是這樣 01/08 19:11
4F：→ FRAXIS: 第一題因為 findmin 是 O(n), decreasekey 是 O(1) 01/08 23:41
5F：→ FRAXIS: 所以複雜度應該是 O(|V|*n + |E| * 1) = O(nV) = (V^2) 01/08 23:42
6F：推 htc018220: Decrease Key 用Fib.heap才是O(1)? 01/09 09:48
7F：→ z3588191: Array decrease key 也是O(1) 01/10 20:28