Złożoność czasowa i pamięciowa
Lekcja 7 z 9 w kursie Algorytm Prima – algorytmy grafowe w Coddy.
Złożoność czasowa:
- Wersja skanująca krawędzie ma tutaj złożoność O(V * E): V-1 rund, w każdej skanowane są wszystkie E krawędzi. Z użyciem kopca binarnego i list sąsiedztwa algorytm Prima działa w czasie O((V + E) log V).
Złożoność pamięciowa:
- O(V) dla tablicy
inTree(plus krawędzie wejściowe).
Podsumowanie:
- Algorytm Prima rozbudowuje jedno drzewo, za każdym razem dodając najtańszą krawędź wychodzącą z niego, aż obejmie wszystkie wierzchołki.
- Daje taki sam minimalny łączny ciężar jak algorytm Kruskala, ale stosuje inną strategię.
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 Prima – 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