Content deleted Content added
O(V^2) complexity for adjacency-matrix search should be O(VE)? |
|||
Line 159:
:If you're going to update this, I think it would make sense to include also a k-ary heap. There seems to be no WP article on it but it's just like a binary heap with a higher branching factor. By using a branching factor of k, one can make the edge update time be O(log(V)/log(k)) at the expense of making the remove-min time go up to O(k log(V)/log(k)) — choosing k=E/V gives an algorithm with total time O(E log(V)/log(E/V)). It's not as good as Fibonacci theoretically but much simpler in practice. —[[User:David Eppstein|David Eppstein]] 03:18, 20 February 2007 (UTC)
:A one-shot search of the adjacency matrix for the minimum edge leaving the tree/cloud is Theta(E), not O(V). Note that you cannot simply check the edges for one of the vertices in the tree. Hence, without any smart bookkepping, which doesn't seem implied, e.g. Cormen's has a complexity of O(VE), not O(V^2). What is the proposed algorithm for the adjacency matrix search with O(V^2) worst-case complexity? [[User:C. lorenz|C. lorenz]] ([[User talk:C. lorenz|talk]]) 16:44, 25 September 2008 (UTC)
== Isn't there anything wrong in the example ? ==
| |||