[理工] 104台大資演 pureblue1234 PTT批踢踢實業坊

作者: pureblue1234 (1234) 2018-01-23 15:15:22

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

作者: a28238341a (小蝸) 2018-01-23 15:56:00

資料結構不一樣

作者: pureblue1234 (1234) 2018-01-23 16:07:00

請問從哪看出資料結構不同，不是只跟你說loser tree,它的樹葉放最小編長嗎?為什麼是Elogv

作者: djmez 2018-01-23 16:17:00

第一題硬幹才會這麼大然後使用非fib (Decrease-key成本不為1)的高度平衡樹做的話成本都是O(VlogV+ElogV)

作者: a28238341a (小蝸) 2018-01-23 16:21:00

我是用推的啦因為1.3題是V^2跟Fib Heap的ElogV打錯了 VlogV+E

作者: djmez 2018-01-23 16:23:00

把P.135看一下然後找各結構的刪除最小、decrease-key帶入就知道了

作者: Dora5566 (咩休幹某) 2018-01-27 17:07:00

prim可以用費波堆積？!

繼續閱讀