algorithm - 如何计算 kruskal 算法的时间复杂度可能是 O(E log E) = O(E log V)。？

Question

请告诉我如何计算克鲁斯卡尔定理的时间复杂度的程序？我知道Kruskal算法的算法但不知道时间复杂度的伪代码和计算......Kruskal算法的复杂度是O(E log E)= O(E log V)(维基百科)。但我不知道如何计算..

Answer 1

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)