Content deleted Content added
O(V^2) complexity for adjacency-matrix search should be O(VE)? |
|||
Line 161:
: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)
::Maintain throughout the algorithm a vector of distances from the tree to the remaining nodes. Whenever each new node is added to the tree, use its row of the distance matrix to update the tree's distance vector. Scanning the tree's distance vector to find each new nodes takes O(V) and updating the distance vector also takes O(V). —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 00:51, 27 September 2008 (UTC)
== Isn't there anything wrong in the example ? ==
| |||