[理工] 104台大資演

[pureblue1234 (1234)]

https://i.imgur.com/iVud8yq.jpg
請問第二題為什麼是O(ElogV)而不是直接寫O(V^2)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.101.11.50
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1516691725.A.86C.html
推 a28238341a: 資料結構不一樣
→ pureblue1234: 請問從哪看出資料結構不同，不是只跟你說loser tree
→ pureblue1234: ,它的樹葉放最小編長嗎?為什麼是Elogv
推 djmez: 第一題硬幹才會這麼大
推 djmez: 然後使用非fib (Decrease-key成本不為1)的高度平衡樹做的
→ djmez: 話成本都是O(VlogV+ElogV)
→ a28238341a: 我是用推的啦 因為1.3題是V^2跟Fib Heap的ElogV
→ a28238341a: 打錯了 VlogV+E
→ djmez: 把P.135看一下 然後找各結構的刪除最小、decrease-key帶入
→ djmez: 就知道了
推 Dora5566: prim可以用費波堆積？!