I was looking at the Wikipedia entry for Prim's algorithm and I noticed that its time complexity with an adjacency matrix is O(V^2) and its time complexity with a heap and adjacency list is O(E lg(V)) where E is the number of edges and V is the number of vertices in the graph.
Since Prim's algorithm is used in denser graphs, E can approach V^2, but when it does, the time complexity with a heap becomes O(V^2 lg(V)) which is greater than O(V^2). Obviously, a heap will improve performance over just searching the array, but the time complexity says otherwise.
How does the algorithm actually slow down with an improvement?
-
Even though the heap saves you from searching through the array, it slows down the "update" part of the algorithm: array updates are O(1), while heap updates are O(log(N)).
In essence, you trade speed in one part of the algorithm for speed in another.
No matter what, you'll have to search N times. However, in dense graphs, you'll need to update a lot (~V^2), and in sparse graphs, you don't.
Another example off the top of my head is searching for elements in an array. If you're only doing it once, linear search is the best - but if you do lots of queries, it's better to sort it and use binary search every time.
-
I think you read it wrong to some degree. For dense graphs, the article talks about using Fibonacci heaps with time complexity O(E + V log V), which is significantly better.
kevmo314 : But even so, as E->V^2, the time complexity reaches O(V^2+Vlog(V)) which is greater than O(V^2).j_random_hacker : -1 sorry. kevmo314's comment explains why.ephemient : O(V^2+Vlog(V)) == O(V^2) That should be obvious after taking an algorithms course...Robert Lamb : My main point was that he kevmo314 read the article wrong to some degree. The article says that Fibonacci heaps are used in graphs dense enough that E = w(v). The article does not mention using Prim's algorithm for denser graphs, it mentions Fibonacci heaps. Dense enough that E=w(V) not E=w(V^2).
0 comments:
Post a Comment