通过改变排序时间的Kruskal算法运行时间

Question

我正在分析最小生成树，想知道排序时间会如何影响Kruskal算法的整体时间复杂性？

示例：

1. 如果可以在O(n log log n)中进行排序
2. 如果可以在O(n)中进行排序

对于这两种情况，答案仍然是O(e log n)吗？还是会改变？

Answer 1

Kruskal算法的时间是O(e log e)，它是对边进行排序的时间。如果你能在O（e）中做到这一点，考虑到找到最小生成树的算法的其余部分是O（e log n），你就有了O(e) + O(e log n)。由于CCD_ 6，则算法时间将是O(n^2 log n)或O(e log n)。如果排序使用相同分析的O（e log log e），则总时间将为O(e log log e)。

详细信息：查找最小生成树的时间是根据对边进行排序所需的时间计算的，然后是一个循环（e次），在该循环中，从排序列表中删除每条边，并检查它是否连接两个不相交的区域。（该检查需要O（logn）），并且循环的时间将是如上所述的O(e log n)。

使用更复杂的不相交集数据结构来查找和检查不相交区域，循环具有O（Eα（V））时间，其中α是单值Ackermann函数（WikiPedia）的极缓慢增长的逆

如果使用不相交集来实现kruskal算法，则复杂度将为SortComplexity+Eα(E)

（E是边的数量，alpha是增长非常慢的函数（根据维基百科，n的实际值小于5）

因此，如果可以在O(n)中进行排序，那么kruskal的复杂性将是O(E α(E))

如果排序复杂度为O(nloglogn)，则kruskal的复杂度将为O(EloglogE)，对于稠密图，则为O(v^2loglogv)（v是顶点数）