[理工] 105交大資演

作者: king8313   2017-12-26 23:19:31
檢討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應該也不會有錯吧?!
謝謝大家~
作者: TampaBayRays (光芒今年拿冠軍)   2017-12-26 23:34:00
57題的e應該是說製作G’要把新的點連到原圖的所有點上,所以是O(V)D錯是因為有負邊,所以一定要用bellman ford46題https://i.imgur.com/2iXot0v.jpghttps://i.imgur.com/J1uTYRC.jpg29題,感覺要說是O(logn)也是可以
作者: howard31622 (howard)   2017-12-27 11:34:00
29題洪逸說都可以就以他的答案為準可能那時沒有人去反應答案
作者: king8313   2017-12-30 00:01:00
感謝兩位大大~

Links booklink

Contact Us: admin [ a t ] ucptt.com