作者cansister (cansister)
看板Grad-ProbAsk
标题[理工] [algo] - MST
时间Tue Jan 5 10:42:10 2010
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
1F：→ assassin88:印象中好像一个是|V|^2一个是|V|^3.. 01/06 00:11
2F：→ FRAXIS:因为|E| = O(|V|^2) 所以 O(|E| lg |E|) = O(|E| lg |V|) 01/06 09:23
3F：→ FRAXIS:到最後写O(|E| lg |V|)就可以了 01/06 09:23
4F：→ cansister:喔喔 感恩 我想了好久，谢谢楼上的解答 01/07 00:53