wake-up-neo.com

O (N log N) Komplexität - Ähnlich wie linear?

Ich glaube, ich werde begraben, weil ich eine so triviale Frage gestellt habe, aber ich bin etwas verwirrt über etwas.

Ich habe QuickSort in Java und C implementiert und einige grundlegende Vergleiche durchgeführt. Das Diagramm wurde als zwei gerade Linien ausgegeben, wobei C 4 ms schneller als das Gegenstück zu Java mit über 100.000 zufälligen Ganzzahlen war.

Results

Den Code für meine Tests finden Sie hier;

Android-Benchmarks

Ich war mir nicht sicher, wie eine (n log n) Linie aussehen würde, aber ich dachte nicht, dass sie gerade sein würde. Ich wollte nur überprüfen, dass dies das erwartete Ergebnis ist und dass ich nicht versuchen sollte, einen Fehler in meinem Code zu finden.

Ich habe die Formel in Excel eingefügt und für Basis 10 scheint es eine gerade Linie mit einem Knick am Anfang zu sein. Liegt es daran, dass der Unterschied zwischen log (n) und log (n + 1) linear zunimmt?

Vielen Dank,

Gav

72
gav

Wenn Sie das Diagramm vergrößern, sehen Sie, dass O (n logn) keine gerade Linie ist. Aber ja, es kommt dem linearen Verhalten ziemlich nahe. Um zu sehen warum, nimm einfach den Logarithmus einiger sehr großer Zahlen.

Zum Beispiel (Basis 10):

log(1000000) = 6
log(1000000000) = 9
…

Um 1.000.000 Zahlen zu sortieren, fügt eine O (n logn) -Sortierung einen Messfaktor 6 hinzu (oder nur ein bisschen mehr, da die meisten Sortieralgorithmen von Logarithmen zur Basis 2 abhängen). Nicht sehr viel.

Tatsächlich ist dieser Log-Faktor so außerordentlich klein, dass etablierte O (n logn) -Algorithmen für die meisten Größenordnungen die linearen Zeitalgorithmen übertreffen. Ein prominentes Beispiel ist die Erstellung einer Suffix-Array-Datenstruktur.

Ein einfacher Fall hat mich kürzlich gebissen als ich versucht habe, eine schnelle Sortierung von kurzen Zeichenfolgen durch die Verwendung von radix sort zu verbessern . Bei kurzen Strings stellte sich heraus, dass diese (zeitlich lineare) Radix-Sortierung schneller war als die Quicksort-Sortierung, aber es gab einen Wendepunkt für noch relativ kurze Strings, da die Radix-Sortierung entscheidend von der Länge der von Ihnen sortierten Strings abhängt.

76
Konrad Rudolph

FYI, Quicksort ist eigentlich O (n ^ 2), aber mit einem durchschnittlichen Fall von O (nlogn)

Zu Ihrer Information, es gibt einen ziemlich großen Unterschied zwischen O(n) und O (nlogn). Deshalb ist es für keine Konstante durch O(n) begrenzt .

Eine grafische Demonstration finden Sie unter:

O(n) vs O(nlogn)

11
groundhog

Wenn Sie noch mehr Spaß haben möchten, zeichnen Sie die Zeit auf, die für n Operationen auf dem Standard disjunkte eingestellte Datenstruktur benötigt wird. Es wurde gezeigt, dass es asymptotisch ist n α ( n) wobei α ( n) die Inverse von - ist. Ackermann-Funktion (obwohl Ihr gewöhnliches Algorithmus-Lehrbuch wahrscheinlich nur eine Grenze von n log log n oder möglicherweise n log * n). Für jede Art von Zahl, auf die Sie wahrscheinlich als Eingabegröße stoßen, ist α ( n) ≤ 5 (und in der Tat log * n ≤ 5) , obwohl es asymptotisch gegen unendlich geht.

Woraus Sie wahrscheinlich lernen können, ist, dass asymptotische Komplexität zwar ein sehr nützliches Werkzeug zum Nachdenken über Algorithmen ist, aber nicht mit praktischer Effizienz identisch ist.

5
  1. Normalerweise haben die Algorithmen O (n * log (n)) eine 2-Basis-Logarithmus-Implementierung.
  2. Für n = 1024 ist log (1024) = 10, also n * log (n) = 1024 * 10 = 10240 Berechnungen, eine Zunahme um eine Größenordnung.

Also ist O (n * log (n)) nur für eine kleine Datenmenge linear.

Tipp: Vergessen Sie nicht, dass Quicksort sich bei zufälligen Daten sehr gut verhält und kein O (n * log (n)) -Algorithmus ist.

3

Beliebige Daten können auf einer Linie dargestellt werden, wenn die Achsen richtig gewählt sind :-)

Wikipedia sagt, dass Big-O der schlechteste Fall ist (dh f(x) ist O(N) bedeutet f(x) ist "oben begrenzt" durch N ) https://en.wikipedia.org/wiki/Big_O_notation

Hier ist eine Sammlung von Grafiken, die die Unterschiede zwischen verschiedenen allgemeinen Funktionen darstellen: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

Die Ableitung von log (x) ist 1/x. So schnell steigt log (x) mit zunehmendem x. Es ist nicht linear, obwohl es wie eine gerade Linie aussehen kann, weil es sich so langsam biegt. Wenn ich an O (log (n)) denke, stelle ich mir O (N ^ 0 +) vor, d. H. Die kleinste Potenz von N, die keine Konstante ist, da jede positive konstante Potenz von N sie schließlich überholt. Es ist nicht 100% genau, also werden Professoren sauer auf dich, wenn du es so erklärst.

Der Unterschied zwischen Protokollen zweier verschiedener Basen ist ein konstanter Multiplikator. Suchen Sie nach der Formel zum Konvertieren von Protokollen zwischen zwei Basen: (unter "Änderung der Basis" hier: https://en.wikipedia.org/wiki/Logarithm ) Der Trick besteht darin, k und b als Konstanten zu behandeln.

In der Praxis gibt es normalerweise einige Probleme mit den von Ihnen aufgezeichneten Daten. Es wird Unterschiede in Dingen außerhalb Ihres Programms geben (etwas, das in die CPU vor Ihrem Programm wechselt, Cache-Fehlschläge usw.). Es dauert viele Läufe, um zuverlässige Daten zu erhalten. Konstanten sind der größte Feind beim Versuch, die Big O-Notation auf die tatsächliche Laufzeit anzuwenden. Ein O(N) -Algorithmus mit einer hohen Konstante kann langsamer sein als ein O (N ^ 2) -Algorithmus für klein genug N.

2
nobodyImportant

log (N) ist (sehr) ungefähr die Anzahl der Stellen in N. Daher gibt es zum größten Teil kaum einen Unterschied zwischen log (n) und log (n + 1).

1
James Curran

Zeichnen Sie eine tatsächliche lineare Linie darüber und Sie werden die kleine Zunahme sehen. Beachten Sie, dass der Y-Wert bei 50.0000 kleiner als der 1/2 Y-Wert bei 100.000 ist.

Es ist da, aber es ist klein. Deshalb ist O(nlog(n)) so gut!

0
Chris Harris