2

I was doing an analysis of minimum spanning trees and was wondering how the sorting time would effect the overall time complexity of Kruskal's algorithm?

Example:

  1. If sorting can be done in O(n log log n)
  2. If sorting can be done in O(n)

Would the answer still remain O(e log n) for both the cases or would it change?

4

2 回答 2

1

如果您使用不相交集来实现 kruskal 算法的复杂性将是 SortComplexity+Eα(E)

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

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

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

于 2014-11-11T08:51:55.463 回答
1

Kruskal 算法的时间是 O(e log e)和它对边进行排序的时间。如果你能在 O(e) 中做到这一点，考虑到找到最小生成树的算法的其余部分是 O(e log n)，你有O(e) + O(e log n). 从那时e=O(n^2)起，算法时间将是O(n^2 log n)或O(e log n)。如果排序需要 O(e log log e) 进行相同的分析，则总时间为O(e log log e).

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

使用更复杂的不相交集数据结构来查找和检查不相交的区域，循环的时间为 O(E α(V))，其中 α 是单值阿克曼函数的增长极其缓慢的逆函数（维基百科）

于 2014-11-11T08:19:22.753 回答