[理工] 交大 101 資演

[olderbrother (大蜘蛛)]

題目
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
推 h56999:46 ，Dij 是greedy  bellman 才是dp
→ h56999:47,48代答案推，應該能得
→ h56999:49， 代5，1，0
→ olderbrother:謝謝大大 <(_ _)>
→ j84255801912:第五題我是想說有n/m個node
→ j84255801912:所以第一步你要和all node的1st data比
→ j84255801912:然後在一node內用binsearch 所以13選b
→ j84255801912:然後insert /del 是先search到該insert的位置 再作搬
→ j84255801912:動 所以O (m/n+logm+m/2(平均）) 我14 15選c
→ j84255801912:18題 因為prims和dijkstra就差在一個是用從src到
→ j84255801912:一個node的dist來選node 而prims是用 一個node
→ j84255801912:到目前集合的距離來選node 所以改那行就變dijkstra
→ j84255801912:o(n^2+m+n)是用adjacency matrix實作 delete min
→ j84255801912:一次花n 共n次所以n^2 ,然後 m*1是decrease key ,n是
→ j84255801912:initialize step
→ olderbrother:謝謝大大 .. <(_ _)>