Kruskal算法的运行时间 [英] Running time of Kruskal's algorithm

问题描述

Kruskal的算法如下：

pre code $ MST-KRUSKAL（G，w）
1. A = {}
2.对于每个顶点v∈GV
3. MAKE-SET（v）
4.按重量将GE的边缘排序为非递减顺序w
5. for每一条边（u，v）∈GE，按照权重不减的顺序取得w
6.如果FIND-SET（u）！= FIND-SET（v）
7. A = AU {（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算法运行多快？如果边权重是从1到W范围内的整数，对于某个常数W？

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

编辑：

另外，假设所有边图中的权重是从1到| V |的整数
。

我认为以下几点：$ b​​
$ b为了使Kruskal算法运行得更快，我们可以使用Counting Sort对边进行排序。

• 第1行需要O（1 ）时间。
  
• 第2-3行需要O（v）时间。


• 第4行需要O（| V | + | E | ）时间。
  
• 第5-8行需要O（| E |α（| V |））time。


• 第9行需要O （1）时间。
  
  
  

  因此，如果我们使用Counting Sort来解决边缘问题，Kruskal的时间复杂度将会

p>






另外：
$ b




如果边的权重是从1到W范围内的整数，对于
，某些常数是W？


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





• 第1行需要O（1）次。


• 第2-3行需要O（| V |）时间。
  
• 第4行需要O（W + | E |）= O（W）+ O（| E |）= O（| E |）= O（| E |）时间。
  
• 第5-8行需要O（| E |α（| V |））时间。
  
• 第9行需要O（1）次。






be：





解决方案




您能解释一下为什么我们推断排序第4行边的时间是O（E * LGE）？


要对一组N个项目进行排序，我们使用快速排序的O（N 总时间复杂度为O（（V + E）α（V））？


我不认为总复杂度是O（（V + E）α（V））。这将是5-8循环的复杂性。 O（（V + E）α（V））复杂度来自V MAKE-SET操作和E Union操作。为了找出为什么我们用α（V）乘以那个值，你需要阅读一些算法书中的不相交集合数据结构的深入分析。






您可以使Kruskal算法运行多快？对于第一部分，第四行，我们有O（E * lg（E））的复杂性，第二部分是第五行， 8，我们有O（（E + V）α（V））的复杂性。这两个总结了收益率O（E lg（E））的复杂度。如果我们使用O（N * lg（N））排序，这是无法改进的。




如果边的权重是整数从1到W的范围为
一些常数W？


如果是这样的话，我们可以使用计数排序第一部分。赋予第4行O（E + W）= O（E）的复杂性。在这种情况下，算法将具有O（（E + V）*α（V））总复杂度。请注意，然而O（E + W）实际上包含一个常量，它可能相当大，对于大W可能不切实际。 $ b




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


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




编辑：



另外，假设图中的所有边权重都是从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 |）），以便于计算。



用这个函数可以得到时间：$ b （1）+ O（| V |）+ O（| V | + | E |）+ O（| E |α（| V |））+ O（1）= O（| V | + |你可以将它简化为O（（| V | + | E |）*α）| O（| E |α（| V |））



（| V |）或O（| V | + | E | *α（| V |）。



V | + | E |）*α（| V |）


对于| W |是类似的。


The Kruskal's algorithm is the following:

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

According to my textbook:

Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(E lgE). The for loop of lines 5-8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest. Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time, where α is a very slowly growing function. Because we assume that G is connected, we have |E| <= |V|-1, and so the disjoint-set operations take O(E α(V)) time. Moreover, since α(V)=O(lgV)=O(lgE), the total running time of Kruskal's algorithm is O(E lgE). Observing that |E|<|V|^2, we have lg |E|=O(lgV), and so we can restate the running time of Kruskal's algorithm as O(E lgV).

Could you explain me why we deduce that the time to sort the edges in line 4 is O(E lgE)? Also how do we get that the total time complexity is O((V+E)α(V)) ?

In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edges weights are integers in the range from 1 to W for some constant W?

How does the time complexity depend on the weight of the edges?

EDIT:

In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run?

I have thought the following:

In order the Kruskal's algorithm to run faster, we can sort the edges applying Counting Sort.

• The line 1 requires O(1) time.
• The lines 2-3 require O(v) time.
• The line 4 requires O(|V|+|E|) time.
• The lines 5-8 require O(|E|α(|V|)) time.
• The line 9 requires O(1) time.

So if we use Counting Sort in order to solve the edges, the time complexity of Kruskal will be

Could you tell me if my idea is right?

Also:

What if the edges weights are integers in the range from 1 to W for some constant W?

We will again use Counting Sort. The algorithm will be the same. We find the time complexity as follows:

• The line 1 requires O(1) time.
• The lines 2-3 require O(|V|) time.
• The line 4 requires O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|) time.
• The lines 5-8 require O(|E|α(|V|)) time.
• The line 9 requires O(1) time.

So the time complexity will be:

解决方案

Could you explain me why we deduce that the time to sort the edges in line 4 is O(E*lgE)?

To sort a set of N items we use O(Nlg(N)) algorithm, which is quick sort, merge sort or heap sort. To sort E edges we therefore need O(Elg(E)) time. This however is not necessary in some cases, as we could use sorting algorithm with better complexity (read further).

Also how do we get that the total time complexity is O((V+E)α(V))?

I don't think total complexity is O((V+E)α(V)). That would be complexity of the 5-8 loop. O((V+E)α(V)) complexity comes from V MAKE-SET operations and E Union operations. To find out why we multiply that with α(V) you will need to read in depth analysis of disjoint set data structure in some algorithmic book.

How fast can you make Kruskal's algorithm run?

For first part, line 4, we have O(E*lg(E)) complexity and for second part, line 5-8, we have O((E+V)α(V)) complexity. This two summed up yield O(Elg(E)) complexity. If we use O(N*lg(N)) sort this can't be improved.

What if the edges weights are integers in the range from 1 to W for some constant W?

If that is the case, than we could use counting sort for first part. Giving line 4 complexity of O(E+W) = O(E). In that case algorithm would have O((E+V)*α(V)) total complexity. Note that however O(E + W) in reality includes a constant that could be rather large and might be impractical for large W.

How does the time complexity depend on the weight of the edges?

As said, if weight of the edges is small enough we can use counting sort and speed up the algorithm.

EDIT:

In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run? I have thought the following:

In order the Kruskal's algorithm to run faster, we can sort the edges applying Counting Sort.

The line 1 requires O(1) time. The lines 2-3 require O(vα(|V|)) time. The line 4 requires O(|V|+|E|) time. The lines 5-8 require O(|E|α(|V|)) time. The line 9 requires O(1) time.

Your idea is correct, however you can make bounds smaller.

The lines 2-3 requires O(|V|) rather than O(|V|α(|V|)). We however simplified it to O(|V|α(|V|)) in previous calculations to make calculations easier.

With this you get the time of: O(1) + O(|V|) + O(|V| + |E|) + O(|E|α(|V|)) + O(1) = O(|V| + |E|) + O(|E|α(|V|))

You can simplify this to either O((|V| + |E|) * α(|V|) or to O(|V| + |E|*α(|V|).

So while you were correct, since O((|V| + |E|) * α(|V|) < O((|V| + |E|) * lg(|E|)

Calculations for the |W| are analogous.

这篇关于Kruskal算法的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！