作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
標題[理工] 104台大資演 5 6 MST
時間Wed Dec 25 17:04:14 2019
https://i.imgur.com/uWGiVpf.jpg
請問5題1 2為什麼是這樣？參考板上答案是左邊的，右邊是我個人寫的
1 我的想法是他都用adjacency list 那不就是用課本的time把E換掉即可？
2 為什麼loser tree是存vertice，我們要選priority queue最小值的不應該是存edge w
eight嗎？
6題為什麼是把combine time換成題目給的，我想說是把2T(n/2)換掉，因為題目給找size
是n/2的時間...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577264656.A.F69.html
1F：→ sjdijojdj: Dijkstra用priority queue來存還沒visit過的點 12/25 18:24
2F：→ sjdijojdj: 每次挑最近的 就是extract-min 共挑v次 12/25 18:25
3F：→ sjdijojdj: 第一題說沒用特別的結構 就用array extact-min花O(v) 12/25 18:26
4F：→ sjdijojdj: Decrease key每次O(1) 共E次 他用adjacency list存 12/25 18:28
5F：→ sjdijojdj: 所以總共O(V^2+E)=O(V^2) 12/25 18:28
6F：→ sjdijojdj: 2 priority queue裡面存的是到某個點的距離 12/25 18:30
7F：→ sjdijojdj: 6 題目說find closest point"between" two sets 12/25 18:32
8F：→ sjdijojdj: T(n/2)是處理一個子集所花的時間 12/25 18:34