我发现随处可见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)
使用二进制堆
使用最小优先级队列,一次调用EXTRACT-MIN(Q)所需的时间复杂度为O(log V).第6行的while循环执行了总计V次.因此EXTRACT-MIN(Q)被称为V次.因此,EXTRACT-MIN(Q)的复杂度为O(V logV).
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).
使用斐波那契堆
因此,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算法的时间复杂度?
发布评论