Time and Space Complexity
Lektion 7 von 9 im Kurs Prims Algorithmus - Graphenalgorithmen von Coddy.
Zeitkomplexität:
- Die Edge-Scan-Version hier ist O(V * E): V-1 Runden, wobei jede alle E Kanten scannt. Mit einem binären Heap und Adjazenzlisten läuft Prim in O((V + E) log V).
Platzkomplexität:
- O(V) für das
inTreeArray (plus die Eingabekanten).
Zusammenfassung:
- Prim lässt einen Baum wachsen, indem er immer die günstigste Kante hinzufügt, die ihn verlässt, bis jeder Knoten enthalten ist.
- Er erzeugt das gleiche minimale Gesamtgewicht wie Kruskal, verwendet jedoch eine andere Strategie.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Prims Algorithmus - Graphenalgorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity