请告诉我如何计算克鲁斯卡尔定理的时间复杂度的程序? 我知道Kruskal算法的算法但不知道时间复杂度的伪代码和计算......Kruskal算法的复杂度是O(E log E)= O(E log V)(维基百科)。但我不知道如何计算..
最佳答案
Kruskal 算法基于森林的联合查找,直到它们形成一棵树。在每一步中,您都使用一条边连接两棵树。
伪代码(来自wikipedia):
tree = {}
for each v:
make-set(v)
for each edge (u,v) ordered by w(u,v):
if find(u) != find(v):
tree.add((u,v))
union(u,v)
return tree
该算法的瓶颈是根据权重对边进行排序。排序最多在 O(nlogn)
中完成,我们正在对大小为 E
的列表进行排序,总共有 O(ElogE)=O(Elog (V^2))=O(2ElogV)=O(ElogV)
关于algorithm - 如何计算 kruskal 算法的时间复杂度可能是 O(E log E) = O(E log V)。?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23057376/