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

[leviliang (levi)]

不好意思，這篇藉著前人的文來問第二小題，第二小題我看網友的答案是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
推 htc018220: 1. E=O(V^1.5)  => O(V^2.5) ?
推 htc018220: 2.O(VlgV+ElgV) => O(VlgV+V^1.5lgV) => O(V^1.5lgV)
→ htc018220: 我的想法也是這樣
→ FRAXIS: 第一題因為 findmin 是 O(n), decreasekey 是 O(1)
→ FRAXIS: 所以複雜度應該是 O(|V|*n + |E| * 1) = O(nV) = (V^2)
推 htc018220: Decrease Key 用Fib.heap才是O(1)?
→ z3588191: Array decrease key 也是O(1)