Time Complexity of Prims Algorithm?

问题:

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:

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.

回答1:

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)

Using a Binary Heap

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).

2. 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).

3. 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).

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).

Using a Fibonacci Heap

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

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).

回答2:

Your idea seems correct. Let's take the complexity as V(lg(v) + E(lg(v))) Then notice that in the inner for loop, we are actually going through all the vertices, and not the edge, so let's modify a little to V(lg(v) + V(lg(v))) which means V(lg(v)) + V*V(lg(v)) But for worst case analysis(dense graphs), V*V is roughly equal to number of edges, E V(lg(v)) + E(lg(v)) (V+E((lg(v)) but since V << E, hence E(lg(v))

回答3:

actually as you are saying as for is nested inside while time complexity should be v.E lg V is correct in case of asymptotic analysis. But in cormen they have done amortized analysis thats why it comes out to be (Elogv)

回答4:

The time complexity of prims algorithm is O(VlogV + ElogV).It is clear to me that you understand how VlogV came.

Now , how does ElogV comes so first look at prims algo

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.Adj[u] 9 if v ∈ Q and w(u, v) < v.key 10 v.π ← u 11 v.key ← w(u, v) }

your problem lies from line 8 to 11 . As you can easily see that line 8 to 11 is executed for every element in Q and we know that number of elements in Q are V . Now consider this for 1st element of Q we run the loop at line 8 for every neighbour of it and we do the same for it's next element and same for every other element of Q . since number of element in Q are equal to V so we run the loop at line 8 exactly 2E times . EX :-

   1
  / \
 2---3

now suppose the element's in Q will be in order 1, 2 ,3 .If we run loop at line 8 for first element of Q i,e 1 , we run it exactly 2 times (we check each of it's neighbours)and for 2 we run loop at line 8 for 2 times and same for 3 . Now we get 2+2+2 = 6(total number of times the loop at line 8 is run ) which is equal to 2*E (where E is total number of edges in graph) so the time complexity for line 8 to 11 becomes

O(2*ElogV) we drop the constants in big-oh notation so complexity becomes

O(ElogV) 

now the total time complexity of the algorithm becomes O(VlogV + ElogV) = O((V+E)logV)

In a dense graph we have E>V , so in the time complexity we ignore V and get

O(ElogV)