Ich habe einen Algorithmus, der zuerst etwas in O(n*log(n)) Zeit und dann tut etwas anderes in O(n^2) Zeit. Bin ich richtig, dass die gesamte KomplexitätWas ist die Komplexität des Codes, die funktioniert O (n * log n) und dann O (n^2) arbeiten?
O(n*log(n) + n^2)
= O(n*(log(n) + n))
= O(n^2)
seit log(n) + n vom + n dominiert wird?
Die Aussage ist korrekt, da O(n log n) eine Teilmenge von O(n^2) ist; Ein formaler Beweis würde jedoch darin bestehen, geeignete Konstanten auszuwählen und zu konstruieren.
Wenn die Rufwahrscheinlichkeit von beiden gleich ist, dann haben Sie Recht. Wenn die Wahrscheinlichkeit für beides nicht gleich ist, müssen Sie eine amortisierte Analyse durchführen, bei der Sie seltene teure Anrufe (n²) in viele schnelle Anrufe (n log (n)) aufteilen.
Für eine schnelle Sortierung (die normalerweise n log (n), aber nur n² benötigt) können Sie nachweisen, dass die durchschnittliche Laufzeit n log (n) aufgrund der amortisierten Analyse ist.
Ich denke, du hast die Frage falsch verstanden. Ich nehme an, dass es sich um einen Algorithmus handelt, der aus zwei Schritten besteht: Einer, der in O (n log n) -Zeit läuft, gefolgt von einem, der in O (n²) -Zeit läuft. Keine Wahrscheinlichkeiten beteiligt. – ruakh
dann ist die Antwort von codor am besten – gartenkralle
eine der Regeln der Komplexitätsanalyse ist, dass Sie die Begriffe mit niedrigeren Exponenten oder niedrigeren Faktoren entfernen müssen.
nlogn vs n^2 (divide both by n)
logn vs n
logn ist kleiner als n ist, als Sie es von der Komplexität Gleichung entfernen
so, wenn die Komplexität O (n log n + n^2) ist, wenn n sehr groß ist, wird der Wert von nlogn ist nicht signifikant im Vergleich zu n^2, das ist, warum Sie es entfernen und neu schreiben als O (n^2)
Das ist richtig, der n² Begriff wäre dominant. –