作者pureblue1234 (1234)
看板Grad-ProbAsk
標題[理工] 104台大資演
時間Tue Jan 23 15:15:22 2018
https://i.imgur.com/iVud8yq.jpg
請問第二題為什麼是O(ElogV)而不是直接寫O(V^2)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.101.11.50
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1516691725.A.86C.html
1F：推 a28238341a: 資料結構不一樣 01/23 15:56
2F：→ pureblue1234: 請問從哪看出資料結構不同，不是只跟你說loser tree 01/23 16:07
3F：→ pureblue1234: ,它的樹葉放最小編長嗎?為什麼是Elogv 01/23 16:07
4F：推 djmez: 第一題硬幹才會這麼大 01/23 16:17
5F：推 djmez: 然後使用非fib (Decrease-key成本不為1)的高度平衡樹做的 01/23 16:19
6F：→ djmez: 話成本都是O(VlogV+ElogV) 01/23 16:19
7F：→ a28238341a: 我是用推的啦 因為1.3題是V^2跟Fib Heap的ElogV 01/23 16:21
8F：→ a28238341a: 打錯了 VlogV+E 01/23 16:22
9F：→ djmez: 把P.135看一下 然後找各結構的刪除最小、decrease-key帶入 01/23 16:23
10F：→ djmez: 就知道了 01/23 16:23
11F：推 Dora5566: prim可以用費波堆積？! 01/27 17:07