מה האלגוריתם הטוב ביותר, ומה זמן הריצה שלו?
Date: 24 Jun 2014 17:03
Number of posts: 2
RSS: New posts
In the MST problem there is no general use for the fact the weights are integers.
Although, Kruskal's algorithm takes O( |E|*a(|V|) ) + Time(Sorting the edges), therefore,
If the weights are not only integers but bounded integers (for example, by a polynomial in |V|)
then they can be sorted quickly and the whole algorithm would take O(|E|*a(|V|)).
(Notice that in some cases you can replace the heap structure in Prim's algorithm with a new data structure
[that used the new assumptions] and reduce the algorithm's complexity to linear complexity.)