https://i.imgur.com/iVud8yq.jpg
請問第二題為什麼是O(ElogV)而不是直接寫O(V^2)
作者: a28238341a (小蝸) 2018-01-23 15:56: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帶入就知道了