作者king8313 ()
看板Grad-ProbAsk
标题[理工] 105交大资演
时间Tue Dec 26 23:19:31 2017
检讨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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1514301574.A.8E0.html
1F：推 TampaBayRays: 57题的e应该是说制作G’要把新的点连到原图的所有点12/26 23:34
2F：→ TampaBayRays: 上，所以是O(V)12/26 23:34
3F：→ TampaBayRays: D错是因为有负边，所以一定要用bellman ford12/26 23:35
4F：推 TampaBayRays: 46题12/26 23:42
!!突然发现我没把57题题目完整放上来，结果答案得从里面找，抱歉哈哈哈感谢你
※ 编辑: king8313 (114.35.118.224), 12/27/2017 00:06:58
7F：→ TampaBayRays: 29题，感觉要说是O(logn)也是可以 12/27 00:20
8F：推 howard31622: 29题洪逸说都可以就以他的答案为准 12/27 11:34
9F：→ howard31622: 可能那时没有人去反应答案 12/27 11:34
10F：→ king8313: 感谢两位大大~ 12/30 00:01