[理工] 104台大資演

看板Grad-ProbAsk作者 (1234)時間8年前 (2018/01/23 15:15), 編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 8年前最新討論串1/1
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
推
01/23 15:56, 8年前 , 1F
資料結構不一樣
01/23 15:56, 1F
→
01/23 16:07, 8年前 , 2F
請問從哪看出資料結構不同，不是只跟你說loser tree
01/23 16:07, 2F
→
01/23 16:07, 8年前 , 3F
,它的樹葉放最小編長嗎?為什麼是Elogv
01/23 16:07, 3F
推
01/23 16:17, 8年前 , 4F
第一題硬幹才會這麼大
01/23 16:17, 4F
推
01/23 16:19, 8年前 , 5F
然後使用非fib (Decrease-key成本不為1)的高度平衡樹做的
01/23 16:19, 5F
→
01/23 16:19, 8年前 , 6F
話成本都是O(VlogV+ElogV)
01/23 16:19, 6F
→
01/23 16:21, 8年前 , 7F
我是用推的啦 因為1.3題是V^2跟Fib Heap的ElogV
01/23 16:21, 7F
→
01/23 16:22, 8年前 , 8F
打錯了 VlogV+E
01/23 16:22, 8F
→
01/23 16:23, 8年前 , 9F
把P.135看一下 然後找各結構的刪除最小、decrease-key帶入
01/23 16:23, 9F
→
01/23 16:23, 8年前 , 10F
就知道了
01/23 16:23, 10F
推
01/27 17:07, 8年前 , 11F
prim可以用費波堆積？!
01/27 17:07, 11F
‣ 更多 pureblue1234 的文章
文章代碼(AID): #1QPk4DXi (Grad-ProbAsk)