Złożoność czasowa i pamięciowa
Lekcja 7 z 9 w kursie Algorytm Kruskala — algorytmy grafowe w Coddy.
Złożoność czasowa:
- Sortowanie E krawędzi zajmuje O(E log E); każda operacja union-find trwa niemal O(1) dzięki kompresji ścieżek, więc klasyczny algorytm Kruskala ma złożoność O(E log E). Wersja z wyborem minimum, którą tutaj tworzymy, ma złożoność O(E2), co jest w porządku dla małych grafów.
Złożoność pamięciowa:
- O(V) na tablicę rodziców (plus krawędzie wejściowe).
Podsumowanie:
- Algorytm Kruskala buduje MST, dodając na każdym kroku najtańszą krawędź, która nie tworzy cyklu, i używa struktury union-find do sprawdzania cykli.
- Wszystkie MST mają tę samą łączną wagę, więc odpowiedź jest unikalna.
Spróbuj swoich sił
Ta lekcja nie zawiera wyzwania z kodem.
Sprawdź sięTa lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.
Wszystkie lekcje w sekcji Algorytm Kruskala — algorytmy grafowe
2Algorytm
Jak to działa?PseudokodImplementacja (część 1)Implementacja (część 2)
Złożoność czasowa i pamięciowaPoćwicz samodzielnie: Kompilator C online