Algorytm Borůvki: Różnice pomiędzy wersjami

Dodane 2 bajty ,  11 lat temu
Poprawiono niedziałający link
m (robot dodaje: cs, es, it, pt, ru)
(Poprawiono niedziałający link)
==Złożoność obliczeniowa==
 
Łatwo udowodnić, że każdym kolejnym wywołaniu liczba wierzchołków zmaleje co najmniej dwukrotnie - zatem wywołań tych będzie co najwyżej <math>log(n)</math>. Złożoność obliczeniowa całości zależy więc od sposobu implementacji kroków 1,2 algorytmu. Zastosowanie w implementacji struktur [[Union-find]] pozwala osiągnąć złożoność na poziomie <math>O(log(n)*m)</math>. Można zmodyfikować go tak, aby osiągnąć złożoność <math>O(log(n)*m - n)</math> - algorytm działa wtedy znacznie szybciej dla grafów rzadkich; dla grafów gęstych modyfikacja nie daje dużych zysków czasowych.
 
 
Anonimowy użytkownik