Prims算法的时间复杂度? [英] Time Complexity of Prims Algorithm?

问题描述

我发现随处可见Prims算法的时间复杂度为 O((V + E)log V)= E log V .但是正如我们所看到的算法:

I found the time complexity of Prims algorithm everywhere as O((V + E) log V) = E log V. But as we can see the algorithm:

似乎时间复杂度是 O(V(log V + E log V)).但是，如果它的时间复杂度是 O((V + E)log V).然后嵌套必须是这样的:

It seems like the time complexity is O(V(log V + E log V)). But if its time complexity is O((V + E) log V). Then the nesting must have to be like this:

但是上面的嵌套似乎是错误的.

But the above nesting is seems to be wrong.

推荐答案

MST-PRIM(G, w, r)
1  for each u ∈ G.V
2       u.key ← ∞
3       u.π ← NIL
4   r.key ← 0
5   Q ← G.V
6   while Q ≠ Ø
7       u ← EXTRACT-MIN(Q)
8       for each v ∈ G.Adjacent[u]
9           if v ∈ Q and w(u, v) < v.key
10              v.π ← u
11              v.key ← w(u, v)

使用二进制堆

1. 使用最小优先级队列，一次调用EXTRACT-MIN(Q)所需的时间复杂度为O(log V).第6行的while循环执行了总计V次.因此EXTRACT-MIN(Q)被称为V次.因此，EXTRACT-MIN(Q)的复杂度为O(V logV).

1. The time complexity required for one call to EXTRACT-MIN(Q) is O(log V) using a min priority queue. The while loop at line 6 is executing total V times.so EXTRACT-MIN(Q) is called V times. So the complexity of EXTRACT-MIN(Q) is O(V logV).

第8行的for循环正在执行总计2E次，因为对于无向图，每个邻接表的长度为2E.通过在最小堆上使用DECREASE_KEY操作，执行第11行所需的时间为O(log v).第11行还执行了总计2E次.因此执行第11行所需的总时间为O(2E logV) = O(E logV).

The for loop at line 8 is executing total 2E times as length of each adjacency lists is 2E for an undirected graph. The time required to execute line 11 is O(log v) by using the DECREASE_KEY operation on the min heap. Line 11 also executes total 2E times. So the total time required to execute line 11 is O(2E logV) = O(E logV).

第1行的for循环将执行V次.使用该过程执行第1至5行将需要O(V).

The for loop at line 1 will be executed V times. Using the procedure to perform lines 1 to 5 will require a complexity of O(V).

MST-PRIM的总时间复杂度是执行步骤1至3总共需要O(VlogV + (E logV + V) = O(E logV)所需的时间复杂度的总和.

Total time complexity of MST-PRIM is the sum of the time complexity required to execute steps 1 through 3 for a total of O(VlogV + (E logV + V) = O(E logV).

使用斐波那契堆

1. 与上述相同.
2. 执行第11行需要O(1)摊销时间.第11行总共执行2E次.因此，总时间复杂度为O(E).
3. 与上述相同

1. Same as above.
2. Executing line 11 requires O(1) amortized time. Line 11 executes a total of 2E times. So the total time complexity is O(E).
3. Same as above

因此，MST-PRIM的总时间复杂度是执行总成本为O(V logV + E + V)=O(E + V logV)的步骤1至3的总和.

So the total time complexity of MST-PRIM is the sum of executing steps 1 through 3 for a total complexity of O(V logV + E + V)=O(E + V logV).

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