關於這題下面回應
(3) 是 v^1.5
想問大家是怎麼算的
謝謝！
※ 引述《mkchiun1028 (YO)》之銘言：
: 倒數第二題，問Prim's演算法worst case的複雜度
: 點數V, 邊數E=V^1.5
: (1) 沒有使用任何data structure
: (2) 使用loser tree，leaf是cost最小的邊
: (3) 使用Fibonacci Heap
: 大家這題寫什麼呢？

VlgV(extra-min)+E*O(1)(decrease-key)=O(V^1.5)想請問一下這題(1)的答案還有(2)得loser tree在這題裡是怎麼運作的?

1的答案好像很多種 我算是O(E + E + E ...+E) V-1次所以是O(VE) = O(V^2.5) (2)需要有人補充 看不懂@@ thx

2我認為 extractmin是跟一般heap一樣動作花logV而decrease key則是從該data對應leaf往上調整花logV所以可以當作heap這樣 整個time O(VlogV+VE)=(V^2.5)1的話我想到的有2種 O(V^2+E),O(V^3)兩種

那我1應該是想錯了。樓上能說說1的部分嗎 感謝！

用一般array+adj list 迴圈+extract min 花V^2,DkeyO(1) 所以是O(V^2+E) 另一種是用matrix 每個vertex的for each v屬於adj(u)這邊要花O(V)*DkeyO (1)=O(V)所以total O(V^3)不過題目是寫用list 所以我寫第一種 但這樣比(2)還XXXXXXXXXXX快...

謝謝各位 1說不能用其他資料結構，是不是也不能用array啊?不用array的話我一開始的想法可能跟yad大類似，一開始隨便挑一個點V0，接著從V0的adjacency list中挑離V0最近的點，V1，再來從V0,V1的list中，挑離目前的樹最近的點，V2，然後從V0,V1,V2的list中，再挑離目前樹最近的點，依此類推每次都花O(E)，總共V次，所以是O(VE)不過我想說，每次選頂點時，應該要考慮這個點是不是已經在樹裡了，所以在掃描adjacency list裡的每一個人時，都要花O(v)的時間，檢查是不是已經在樹裡了，所以總共要花O(E*V^2)=O(V^3.5)的時間，不是很確定