[理工] 交大 101 資演

看板Grad-ProbAsk作者 (大蜘蛛)時間10年前 (2014/02/10 20:45), 編輯推噓1(1推 0噓 15→)
留言16則, 3人參與, 最新討論串1/3 (看更多)
題目 http://www.lib.nctu.edu.tw/attach/download/id-1532/ 問題.. 有點多 爬文找不到，自己想不通.. 5. (13)B (14)C (15)C 請問這些複雜度是怎麼求出來的？ 14. (40)A (41)E (42)B 一樣，這些複雜度是怎麼求出來的？ 16. (46)C (47)B (48)B 這些答案不知道怎麼出來的 @@ 17. (49)B (50)E (51)E N=10 就湊不出答案了@@ 不知道這答案怎麼出來的 18. (52)D 這個 mystery 是 Prim 嘛？ (53)A 這樣換的話 會變成 Dijkstra 嘛？ (54)E 如果他是 Prim 的話 應該是 O(n^2) 那 O(n^2 + (m+n)) 是？ 19. (55)E (56)C (57)D 這些答案不知道怎麼出來的？ 不好意思問題有點多，麻煩大家了 <(_ _)> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.223.254.189
推
02/11 01:34, , 1F
46 ，Dij 是greedy bellman 才是dp
02/11 01:34, 1F
→
02/11 01:34, , 2F
47,48代答案推，應該能得
02/11 01:34, 2F
→
02/11 01:37, , 3F
49， 代5，1，0
02/11 01:37, 3F
→
02/11 21:13, , 4F
謝謝大大 <(_ _)>
02/11 21:13, 4F
→
02/13 11:23, , 5F
第五題我是想說有n/m個node
02/13 11:23, 5F
→
02/13 11:24, , 6F
所以第一步你要和all node的1st data比
02/13 11:24, 6F
→
02/13 11:25, , 7F
然後在一node內用binsearch 所以13選b
02/13 11:25, 7F
→
02/13 11:27, , 8F
然後insert /del 是先search到該insert的位置 再作搬
02/13 11:27, 8F
→
02/13 11:28, , 9F
動 所以O (m/n+logm+m/2(平均）) 我14 15選c
02/13 11:28, 9F
→
02/13 11:36, , 10F
18題 因為prims和dijkstra就差在一個是用從src到
02/13 11:36, 10F
→
02/13 11:36, , 11F
一個node的dist來選node 而prims是用 一個node
02/13 11:36, 11F
→
02/13 11:37, , 12F
到目前集合的距離來選node 所以改那行就變dijkstra
02/13 11:37, 12F
→
02/13 11:38, , 13F
o(n^2+m+n)是用adjacency matrix實作 delete min
02/13 11:38, 13F
→
02/13 11:40, , 14F
一次花n 共n次所以n^2 ,然後 m*1是decrease key ,n是
02/13 11:40, 14F
→
02/13 11:40, , 15F
initialize step
02/13 11:40, 15F
→
02/18 19:01, , 16F
謝謝大大 .. <(_ _)>
02/18 19:01, 16F
‣ 更多 olderbrother 的文章
文章代碼(AID): #1I-CdR95 (Grad-ProbAsk)
‣ 更多 olderbrother 的文章
文章代碼(AID): #1I-CdR95 (Grad-ProbAsk)