推 easonc: VlgV(extra-min)+E*O(1)(decrease-key)=O(V^1.5) 02/10 09:03
→ easonc: 想請問一下這題(1)的答案還有(2)得loser tree在這題裡是怎 02/10 09:09
→ easonc: 麼運作的? 02/10 09:09
→ yad50968: 1的答案好像很多種 我算是O(E + E + E ...+E) V-1次 02/10 12:18
→ yad50968: 所以是O(VE) = O(V^2.5) (2)需要有人補充 看不懂@@ thx 02/10 12:19
→ jerry031181: 2我認為 extractmin是跟一般heap一樣動作花logV 02/10 12:33
→ jerry031181: 而decrease key則是從該data對應leaf往上調整花logV 02/10 12:33
→ jerry031181: 所以可以當作heap這樣 整個time O(VlogV+VE)=(V^2.5) 02/10 12:34
→ jerry031181: 1的話我想到的有2種 O(V^2+E),O(V^3)兩種 02/10 12:37
→ yad50968: 那我1應該是想錯了。樓上能說說1的部分嗎 感謝！ 02/10 13:16
→ jerry031181: 用一般array+adj list 迴圈+extract min 花V^2,Dkey 02/10 14:25
→ jerry031181: O(1) 所以是O(V^2+E) 另一種是用matrix 每個vertex的 02/10 14:27
→ jerry031181: for each v屬於adj(u)這邊要花O(V)*DkeyO (1)=O(V) 02/10 14:28
→ jerry031181: 所以total O(V^3) 02/10 14:28
→ jerry031181: 不過題目是寫用list 所以我寫第一種 但這樣比(2)還 02/10 14:30
→ jerry031181: XXXXXXXXXXX快... 02/10 14:30
→ easonc: 謝謝各位 1說不能用其他資料結構，是不是也不能用array啊? 02/10 17:06
→ easonc: 不用array的話我一開始的想法可能跟yad大類似，一開始隨便 02/10 17:08
→ easonc: 挑一個點V0，接著從V0的adjacency list中挑離V0最近的點， 02/10 17:09
→ easonc: V1，再來從V0,V1的list中，挑離目前的樹最近的點，V2，然 02/10 17:11
→ easonc: 後從V0,V1,V2的list中，再挑離目前樹最近的點，依此類推 02/10 17:12
→ easonc: 每次都花O(E)，總共V次，所以是O(VE) 02/10 17:13
→ easonc: 不過我想說，每次選頂點時，應該要考慮這個點是不是已經在 02/10 17:16
→ easonc: 樹裡了，所以在掃描adjacency list裡的每一個人時，都要花 02/10 17:17
→ easonc: O(v)的時間，檢查是不是已經在樹裡了，所以總共要花 02/10 17:18
→ easonc: O(E*V^2)=O(V^3.5)的時間，不是很確定 02/10 17:20
→ DLHZ: 在選的時候就能決定在不在樹裡了 不影響 12/19 23:00