n ^ 2 log n Komplexität
oder wir behalten das Protokoll? 4 Antworten
Wenn das die Zeit-Komplexität des Algorithmus ist, dann ist es schon in der großen O-Notation, also, ja, behalten Sie das Protokoll. Asymptotisch gibt es einen Unterschied zwischen O(n^2) und O((n^2)*log(n)) .
Ein einfacher Weg, die große O-Notation zu verstehen, besteht darin, die tatsächliche Anzahl atomarer Schritte durch den Ausdruck mit dem großen O zu teilen und zu validieren, dass man eine Konstante erhält (oder einen Wert, der kleiner ist als eine Konstante).
zum Beispiel, wenn Ihr Algorithmus 10n²⋅logn Schritte:
10n²⋅logn / n² = 10 log n - & gt; nicht konstant in n - & gt; 10n²⋅log n ist nicht O (n²)
10n²⋅logn / (n²⋅log n) = 10 - & gt; Konstante in n - & gt; 10n²⋅log n ist O (n²⋅logn)
Sie behalten das Protokoll, da log (n) mit steigendem n zunimmt und Ihre Komplexität insgesamt erhöht, da es multipliziert wird.
Als allgemeine Regel würden Sie nur Konstanten entfernen. Wenn Sie zum Beispiel O (2 * n ^ 2) hätten, würden Sie einfach sagen, dass die Komplexität O (n ^ 2) ist, da die Ausführung auf einer Maschine, die doppelt so leistungsstark ist, die Komplexität nicht beeinflussen sollte.
Wenn Sie die Komplexität O (n ^ 2 + n ^ 2) hätten, würden Sie genauso zu dem obigen Fall kommen und einfach sagen, dass es O (n ^ 2) ist. Da O (log (n)) optimaler ist als O (n ^ 2), würden Sie, wenn Sie O (n ^ 2 + log (n)) hätten, die Komplexität als O (n ^ 2) bezeichnen, weil es noch weniger ist als mit O (2 * n ^ 2).
O (n ^ 2 * log (n)) fällt nicht in die obige Situation, also sollten Sie es nicht vereinfachen.
Tags und Links time-complexity big-o