Big o Notation von Algorithmus, bestehend aus kleineren Algorithmen
-
21-12-2019 - |
Frage
Ich arbeite an einer Zuweisung, die ein Diagramm annimmt, fügt der Grafik einen zusätzlichen Scheitelpunkt hinzu, wendet Bellman Ford mit dem neuen Scheitelpunkt als Quelle an, wodurch die gesamten Paare von Dijkstra an das Graph verwendet werden.
Die verwendeten Algorithmen verfügen über Laufzeiten / Platzbedarf von:
generasacodicetagpre.Ich habe Schwierigkeiten, das Verständnis zu verstehen, ob ich das große O des Gesamtprozesses berechne.Jedes Programm wird separat ausgeführt, und der Ausgang wird vom Programm zum Programm geleitet.Mein obwohl der Gesamtalgorithmus ist, hätte eine große Laufzeit von:
o (v + eV + eV log v) , die auf
Der Platzbedarf würde auf ähnliche Weise berechnet.Ich denke an das richtig?Danke!
Lösung
Genau, eine "Faustregel" ist, dass in einer Folge von Codeblöcken die Gesamtkomplexität von dem Block mit größter Komplexität (asymptotisch) dominiert wird
materatisch, wenn v zu sehr großen Zahlen neigt, ist es kleiner als eV, was kleiner ist als Evlogv.Für große V wird die Komplexität Ihres Algorithmus also gut von Evlogv
angenähert