克鲁斯卡尔算法的运行时间

Question

克鲁斯卡尔算法的运行时间

8

Kruskal算法的步骤如下：

MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3.      MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6.      if FIND-SET(u)!=FIND-SET(v)   
7.         A=A U {(u,v)}  
8.         Union(u,v)
9. return A

根据我的教材：

在第1行初始化集合A需要O(1)时间，在第4行对边进行排序的时间为O(E lgE)。第5-8行的循环在不相交集森林上执行O(E)个FIND-SET和UNION操作。加上|V|个MAKE-SET操作，这些操作总共需要O((V+E)α(V))的时间，其中α是一个非常缓慢增长的函数。因为我们假设G是连通的，所以有|E| <= |V|-1，因此不相交集操作需要O(E α(V))的时间。此外，由于α(V)=O(lgV)=O(lgE)，Kruskal算法的总运行时间为O(E lgE)。观察到|E| < |V|^2，因此lg |E|=O(lgV)，因此我们可以将Kruskal算法的运行时间重新表述为O(E lgV)。

你能解释一下为什么我们得出的结论是线4中对边进行排序的时间复杂度为O(E lgE)吗？另外，我们如何得出总时间复杂度为O((V+E)α(V))？

此外，假设图中所有边的权重都是从1到|V|的整数。你能让Kruskal算法运行得更快吗？如果边的权重是范围从1到某个常数W的整数，会怎样？时间复杂度如何取决于边的权重？

编辑：

此外，假设图中所有边的权重都是从1到|V|的整数。你能让Kruskal算法运行得更快吗？我想到了以下方法：

为了使Kruskal算法运行更快，我们可以使用计数排序对边进行排序。

- 第1行需要O(1)时间。 - 第2-3行需要O(v)时间。 - 第4行需要O(|V|+|E|)时间。 - 第5-8行需要O(|E|α(|V|))时间。 - 第9行需要O(1)时间。

因此，如果我们使用计数排序来解决边，Kruskal的时间复杂度将为

O(E + V log V)

请问我的想法是否正确？

另外：

如果边的权重是范围从1到某个常数W的整数，会怎样？

我们将再次使用计数排序。算法将保持不变。我们按以下方式找到时间复杂度：

第一行需要O(1)时间。
第二至三行需要O(|V|)时间。
第四行需要O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|)时间。
第五至八行需要O(|E|α(|V|))时间。
第九行需要O(1)时间。

因此时间复杂度为：

enter image description here

- Mary Star

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Neithrik · Accepted Answer

可以解释一下为什么我们推断出第4行中对边进行排序的时间是O(E* lgE)吗？

要对N个项目进行排序，我们使用O(Nlg(N))算法，即快速排序、归并排序或堆排序。因此，要对E条边进行排序，我们需要O(Elg(E))的时间。然而，在某些情况下，这不是必要的，因为我们可以使用具有更好复杂度的排序算法（请继续阅读）。

另外，我们如何得出总的时间复杂度为O((V+E)α(V))？

我不认为总的复杂度是O((V+E)α(V))。那将是5-8循环的复杂度。O((V+E)α(V))的复杂度来自于V MAKE-SET操作和E Union操作。要了解为什么我们要将其乘以α(V)，您需要在一些算法书籍中深入分析不相交集数据结构。

你能让Kruskal算法运行得多快？

对于第一部分，第4行，我们具有O(E*lg(E))的复杂度，对于第二部分，第5-8行，我们具有O((E+V)α(V))的复杂度。这两者加起来得到O(Elg(E))的复杂度。如果我们使用O(Nlg(N))排序，这不能改进。

如果边权重是1到W的整数，该怎么办？

如果是这种情况，我们可以使用计数排序进行第一部分。给出第4行的复杂度为O(E+W)=O(E)。在这种情况下，算法将具有O((E+V)*α(V))的总复杂度。请注意，然而，实际上O(E + W)包括一个可能相当大的常数，对于大的W可能是不切实际的。

时间复杂度如何取决于边的权重？

正如所说，如果边的权重足够小，我们可以使用计数排序来加速算法。

此外，假设图中所有边的权重都是从1到|V|的整数，你能让Kruskal算法运行得多快？我想到了以下内容：

为了使Kruskal算法运行更快，我们可以应用计数排序对边进行排序。第1行需要O(1)时间。第2-3行需要O(vα(|V|))时间。第4行需要O(|V|+|E|)时间。第5-8行需要O(|E|α(|V|))时间。第9行需要O(1)时间。

您的想法是正确的，但您可以使界限更小。

第2-3行需要O（|V|）而不是O（|V|α（|V|））。但我们在之前的计算中将其简化为O（|V|α（|V|）），以使计算更容易。

因此，您可以得到以下时间： O（1）+ O（|V|）+ O（|V| + |E|）+ O（|E|α（|V|））+ O（1）= O（|V| + |E|）+ O（|E|α（|V|））

您可以将其简化为O（（|V| + |E|）* α（|V|）或O（|V| + |E|*α（|V|）。

因此，尽管您是正确的，因为O（（|V| + |E|）* α（|V|）< O（（|V| + |E|）* lg（|E|） |W|的计算类似。