→ assassin88:印象中好像一個是|V|^2一個是|V|^3.. 01/06 00:11
→ FRAXIS:因為|E| = O(|V|^2) 所以 O(|E| lg |E|) = O(|E| lg |V|) 01/06 09:23
→ FRAXIS:到最後寫O(|E| lg |V|)就可以了 01/06 09:23
→ cansister:喔喔 感恩 我想了好久，謝謝樓上的解答 01/07 00:53
97交大資訊學院資料結構與演算法
Minimum spanning tree
(4) If adjacency matrix is used,what are the time complexity of Kruskal's and
Prim's algorithms?(2%)
沒有解答不好意思
Prim's algorithm 的話，我認為應該是O(|V|^2)，
Kruskal's algorithm的話，我不是很清楚，不過下面是我的想法
分成兩個步驟：
1. 對所有edges作sorting，因為需要將|V|*|V|矩陣所有的邊取出需 O(|V|^2)，
再作sorting需 O(|E|log|E|)。
2. 利用disjoint sets來檢查是否cycle產生，需O(|E|log|V|)
由1、2得O(|V|^2)+O(|E|log|E|)+O(|E|log|V|)
請問結果應該要怎麼化簡呢？還是我的想法哪邊有問題，謝謝指教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.129.184