作者YuxiWen (yu)
看板Grad-ProbAsk
標題[資工] [資演] 台大 105 [1d] [5a]
時間Sun Feb 5 16:26:27 2017
第一題題目
http://i.imgur.com/dtQYCeL.jpg
想請問d選項
我知道的建立heap的方法有
top-dowm(動態建立)需時間(nlogn)
bottom-up(須知道所有的點)需時間(n)
所以這題是指哪一個呢？
第5a題題目
http://i.imgur.com/w2ib3BN.jpg
http://i.imgur.com/udbVu5f.jpg
想請問a小題題目有沒有除了暴力解以外比較快的方法的方法?
我一開始傻傻的用Dijkstra 方法，想說答案最準確，結果發現超過4個邊...
只好暴力解
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.245.187
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486283190.A.846.html
推 w181496: Bottom up建heap是O(n)吧02/05 16:29
對耶，忘記了
推 aa06697: 第一題bottom up是O(n) 沒特別講都是指bottom up吧～ 第02/05 16:29
原來如此!
→ aa06697: 五題我是用bellman但for loop只跑四次02/05 16:29
!!!原來還有這招，感謝!
※ 編輯: YuxiWen (114.137.245.187), 02/05/2017 16:47:23
→ yupog2003: 用Bellmanford只跑四次好聰明，當初採用瘋狂確認法...02/05 16:36
※ 編輯: YuxiWen (114.137.245.187), 02/05/2017 16:47:41