Kruskal算法的运行时间

Question

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行的for循环在不相交的林上执行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的算法？如果对于某些常数W,边缘权重是1到W范围内的整数怎么办？

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

编辑:

另外,假设图中的所有边权重是从1到| V |的整数.你能以多快的速度运行Kruskal的算法？

我想到了以下几点:

为了使Kruskal算法运行得更快,我们可以使用Counting Sort对边进行排序.

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

因此,如果我们使用Counting Sort来解决边缘,那么Kruskal的时间复杂度将是

你能告诉我我的想法是否正确吗？

也:

如果对于某些常数W,边缘权重是1到W范围内的整数怎么办？

我们将再次使用Counting Sort.算法将是相同的.我们发现时间复杂度如下:

• 第1行需要O(1)时间.
• 第2-3行需要O(| V |)时间.
• 线4需要O(W + | E |)= O(W)+ O(| E |)= O(1)+ O(| E |)= O(| E |)时间.
• 线5-8需要O(| E |α(| V |))时间.
• 第9行需要O(1)时间.

所以时间的复杂性将是:

Answer 1

你能解释一下为什么我们推断出第4行的边缘排序时间是O(E*lgE)吗？

为了对一组N个项进行排序,我们使用O(N lg(N))算法,即快速排序,合并排序或堆排序.因此,为了排序E边缘,我们需要O(E lg(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(E lg(E))的复杂性.如果我们使用O(N*lg(N))排序,则无法改进.

如果对于某些常数W,边缘权重是1到W范围内的整数怎么办？

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

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

如上所述,如果边缘的重量足够小,我们可以使用计数排序并加速算法.

编辑:

另外,假设图中的所有边权重是从1到| V |的整数.你能以多快的速度运行Kruskal的算法？我想到了以下几点:

为了使Kruskal算法运行得更快,我们可以使用Counting Sort对边进行排序.

第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 | 是类似的.