[理工] 105交大資演

看板Grad-ProbAsk作者時間6年前 (2017/12/26 23:19), 6年前編輯推噓4(4推 0噓 6→)
留言10則, 3人參與, 6年前最新討論串4/10 (看更多)
檢討105交大資演時我把先前板上的發問都看完了，但還是有些問題麻煩大家了~ https://i.imgur.com/RPEdJuL.jpg
29. (c)選項 要merge Fibonacci heap不是花費O(logn)嗎，因為Fibonacci是binomial的延伸，如果不 是採取lazy merge應該是log n? https://i.imgur.com/RmGwdnE.jpg
32. 我只能理解沒發生碰撞的機率是(1-m/n)但不太了解倒數是insert cost... https://i.imgur.com/0DIm7hC.jpg
46. (d)選項 雖然e錯比較明顯，但如果要用BFS條件不是unweighted嗎，跟DAG也有關係嗎? https://i.imgur.com/Kam4xPk.jpg
57. (e)選項 要reweight的成本不是跑一次Bellmon-Ford，耗時O(VE)嗎?怎麼只要O(V) 另外(d)選項就算reweight後繼續用Bellmon-Ford應該也不會有錯吧?! 謝謝大家~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1514301574.A.8E0.html
推
12/26 23:34, 6年前 , 1F
57題的e應該是說製作G’要把新的點連到原圖的所有點
12/26 23:34, 1F
→
12/26 23:34, 6年前 , 2F
上，所以是O(V)
12/26 23:34, 2F
→
12/26 23:35, 6年前 , 3F
D錯是因為有負邊，所以一定要用bellman ford
12/26 23:35, 3F
推
12/26 23:42, 6年前 , 4F
46題
12/26 23:42, 4F
→
12/26 23:42, 6年前 , 5F
12/26 23:42, 5F
!!突然發現我沒把57題題目完整放上來，結果答案得從裡面找，抱歉哈哈哈感謝你 ※ 編輯: king8313 (114.35.118.224), 12/27/2017 00:06:58
推
12/27 00:20, 6年前 , 6F
12/27 00:20, 6F
→
12/27 00:20, 6年前 , 7F
29題，感覺要說是O(logn)也是可以
12/27 00:20, 7F
推
12/27 11:34, 6年前 , 8F
29題洪逸說都可以就以他的答案為準
12/27 11:34, 8F
→
12/27 11:34, 6年前 , 9F
可能那時沒有人去反應答案
12/27 11:34, 9F
→
12/30 00:01, 6年前 , 10F
感謝兩位大大~
12/30 00:01, 10F
‣ 更多 king8313 的文章
文章代碼(AID): #1QGcY6ZW (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 4 之 10 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 king8313 的文章
文章代碼(AID): #1QGcY6ZW (Grad-ProbAsk)