Jedes anständige Lehrbuch über Algorithmen wird erklären, wie schnell Sortieralgorithmen wie Quicksort und Heapsort sind, aber man braucht keine verrückte Mathematik, um zu beweisen, dass sie asymptotisch so schnell sind, wie es nur geht.
Eine pedantische Anmerkung zur Notation
Die meisten Informatiker verwenden die Big-O-Notation, um „asymptotisch gleich, bis zu einem konstanten Skalierungsfaktor“ zu meinen, was nicht ganz das ist, was es für andere Mathematiker bedeutet. Tut mir leid, ich werde die Big-O-Schreibweise wie in den CS-Lehrbüchern verwenden, aber zumindest werde ich sie nicht mit anderen mathematischen Schreibweisen verwechseln.
Vergleichsbasierte Sortierung
Betrachten wir den Spezialfall von Algorithmen, die zwei Werte auf einmal vergleichen (wie Quicksort und Heapsort und die meisten anderen populären Algorithmen). Die Ideen können später auf alle Sortieralgorithmen ausgedehnt werden.
Ein einfaches Zählargument für den schlimmsten Fall
Angenommen, man hat ein Array mit vier Elementen, alle unterschiedlich, in zufälliger Reihenfolge. Kann man es sortieren, indem man nur ein Paar von Elementen vergleicht? Offensichtlich nicht, aber es gibt einen guten Grund, der das Gegenteil beweist: Um die Anordnung zu sortieren, muss man wissen, wie man die Elemente neu anordnet, um sie in die richtige Reihenfolge zu bringen. Mit anderen Worten, man muss wissen, welche Permutation benötigt wird. Wie viele mögliche Permutationen gibt es? Das erste Element kann an einen von vier Plätzen verschoben werden, das zweite an einen der verbleibenden drei, für das dritte gibt es zwei Möglichkeiten, und das letzte Element muss den einen verbleibenden Platz einnehmen. Es gibt also 4×3×2×1=4!=244 \mal 3 \mal 2 \mal 1 = 4! = 24 mögliche Permutationen, aus denen man wählen kann, aber es gibt nur zwei mögliche Ergebnisse, wenn man zwei verschiedene Dinge vergleicht: „GRÖSSER“ und „KLEINER“. Wenn du eine Liste aller möglichen Permutationen erstellst, könntest du entscheiden, dass „GRÖSSER“ bedeutet, dass du Permutation Nr. 8 brauchst und „KLEINER“ bedeutet, dass du Permutation Nr. 24 brauchst, aber es gibt keine Möglichkeit zu wissen, wann du die anderen 22 Permutationen brauchst.
Mit zwei Vergleichen hast du 2×2=42 \mal 2 = 4 mögliche Ergebnisse, was immer noch nicht genug ist. Man kann nicht jede mögliche gemischte Anordnung sortieren, wenn man nicht mindestens fünf Vergleiche durchführt (25=322^5 = 32). Wenn W(N)W(N) die Anzahl der Vergleiche ist, die im schlimmsten Fall benötigt werden, um NN verschiedene Elemente mit einem Algorithmus zu sortieren, können wir sagen
2W(N)≥N!2^{W(N)} \geq N!
Nimmt man einen Logarithmus zur Basis 2,
W(N)≥log2N!W(N) \geq \log_2{N!}
Asymptotisch wächst N!N! wächst wie NNN^N (siehe auch Stirlings Formel), also
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
Und das ist eine O(NlogN)O(N\log N)-Grenze für den schlimmsten Fall, nur durch Zählen der Ausgaben.
Durchschnittsfall aus der Informationstheorie
Wir können ein stärkeres Ergebnis erhalten, wenn wir das Zählargument mit ein wenig Informationstheorie erweitern. So könnten wir einen Sortieralgorithmus als Code für die Übermittlung von Informationen verwenden:
- Ich denke an eine Zahl – sagen wir 15
- Ich suche die Permutation #15 aus der Liste der Permutationen von vier Elementen
- Ich führe den Sortieralgorithmus für diese Permutation aus und zeichne alle „GRÖSSER“- und „KLEINER“-Vergleichsergebnisse auf
- Ich übermittle Ihnen die Vergleichsergebnisse in binärem Code
- Sie spielen meinen Sortieralgorithmus nach, Schritt für Schritt, wobei Sie sich bei Bedarf auf meine Liste der Vergleichsergebnisse beziehen
- Nun, da Sie wissen, wie ich mein Array umgeordnet habe, um es zu sortieren, können Sie die Permutation umkehren, um mein ursprüngliches Array herauszufinden
- Sie sehen mein ursprüngliches Array in der Permutationsliste nach, um herauszufinden, dass ich die Zahl 15 übermittelt habe
Okay, es ist ein bisschen seltsam, aber es ist machbar. Das bedeutet, dass für Sortieralgorithmen dieselben Gesetze gelten wie für normale Kodierungsverfahren, einschließlich des Theorems, das beweist, dass es keinen universellen Datenkompressor gibt. Ich habe für jeden Vergleich, den der Algorithmus durchführt, ein Bit übertragen, also muss die Anzahl der Vergleiche im Durchschnitt mindestens so groß sein wie die Anzahl der Bits, die zur Darstellung meiner Daten erforderlich sind, so die Informationstheorie. Genauer gesagt muss die durchschnittliche Anzahl der Vergleiche mindestens der Shannon-Entropie meiner Eingabedaten entsprechen, gemessen in Bits. Die Entropie ist ein mathematisches Maß für den Informationsgehalt oder die Unvorhersehbarkeit einer Sache.
Wenn ich eine Anordnung von NN-Elementen habe, die ohne Verzerrung in jeder möglichen Reihenfolge angeordnet sein könnten, dann ist die Entropie maximiert und beträgt log2N!\log_2{N!} Bits. Das beweist, dass O(NlogN)O(N\log{N}) ein optimaler Mittelwert für eine vergleichsbasierte Sortierung mit beliebiger Eingabe ist.
Das ist die Theorie, aber wie sehen reale Sortieralgorithmen aus? Im Folgenden ist die durchschnittliche Anzahl der Vergleiche dargestellt, die zum Sortieren eines Arrays erforderlich sind. Ich habe das theoretische Optimum mit der naiven Quicksort-Sortierung und der Ford-Johnson Merge-Insertion-Sortierung verglichen, die darauf ausgelegt ist, Vergleiche zu minimieren (obwohl sie insgesamt selten schneller ist als Quicksort, weil es im Leben um mehr geht als um die Minimierung von Vergleichen). Seit ihrer Entwicklung im Jahr 1959 wurde die Merge-Insertion-Sortierung optimiert, um ein paar mehr Vergleiche herauszuholen, aber die Grafik zeigt, dass sie bereits fast optimal ist.
Es ist schön, wenn ein wenig Theorie ein so gutes praktisches Ergebnis liefert.
Zusammenfassung bis jetzt
Hier ist, was bis jetzt bewiesen wurde:
- Wenn das Array in beliebiger Reihenfolge beginnen kann, sind im schlimmsten Fall mindestens O(NlogN)O(N\log{N}) Vergleiche nötig
- Die durchschnittliche Anzahl der Vergleiche muss mindestens der Entropie des Arrays entsprechen, was für eine zufällige Eingabe O(NlogN)O(N\log{N}) ist
Anmerkung, dass #2 es ermöglicht, dass vergleichsbasierte Sortieralgorithmen schneller als O(NlogN)O(N\log{N}) sind, wenn die Eingabe eine niedrige Entropie hat (mit anderen Worten, besser vorhersehbar ist). Die Merge-Sortierung liegt nahe bei O(N)O(N), wenn die Eingabe viele sortierte Teilfelder enthält. Insertion Sort liegt nahe bei O(N)O(N), wenn die Eingabe ein Array ist, das sortiert wurde, bevor es ein wenig gestört wurde. Keiner dieser Algorithmen ist im schlimmsten Fall besser als O(NlogN)O(N\log{N}), es sei denn, einige Array-Ordnungen sind als Eingaben unmöglich.
Allgemeine Sortieralgorithmen
Vergleichsbasierte Sortierungen sind in der Praxis ein interessanter Spezialfall, aber es gibt nichts theoretisch Besonderes anCMP im Gegensatz zu jeder anderen Anweisung auf einem Computer. Beide obigen Argumente können auf jeden Sortieralgorithmus verallgemeinert werden, wenn man ein paar Dinge beachtet:
- Die meisten Computerbefehle haben mehr als zwei mögliche Ausgaben, aber immer noch eine begrenzte Anzahl
- Die begrenzte Anzahl von Ausgaben bedeutet, dass ein Befehl nur eine begrenzte Menge an Entropie verarbeiten kann
Das gibt uns dieselbe O(NlogN)O(N\log{N})-Untergrenze für die Anzahl der Befehle. Jeder physikalisch realisierbare Computer kann nur eine begrenzte Anzahl von Instruktionen gleichzeitig verarbeiten, also ist das auch eine O(NlogN)O(N\log{N}) untere Schranke für die benötigte Zeit.
Aber was ist mit „schnelleren“ Algorithmen?
Die nützlichste praktische Implikation der allgemeinen O(NlogN)O(N\log{N}) Schranke ist, dass wenn man von einem asymptotisch schnelleren Algorithmus hört, man weiß, dass er irgendwie „schummeln“ muss. Es muss einen Haken geben, der bedeutet, dass es sich nicht um einen Allzweck-Sortieralgorithmus handelt, der auf beliebig große Arrays skaliert. Es könnte immer noch ein nützlicher Algorithmus sein, aber es ist eine gute Idee, das Kleingedruckte genau zu lesen.
Ein bekanntes Beispiel ist die Radix-Sortierung. Er wird oft als O(N)O(N) Sortieralgorithmus bezeichnet, aber der Haken ist, dass er nur funktioniert, wenn alle Zahlen in kk Bits passen, und in Wirklichkeit ist er O(kN)O(kN).
Was bedeutet das in der Praxis? Nehmen wir an, Sie haben eine 8-Bit-Maschine. Sie können 28=2562^8 = 256 verschiedene Zahlen in 8 Bits darstellen, wenn Sie also ein Array mit Tausenden von Zahlen haben, werden Sie Duplikate haben. Für einige Anwendungen mag das in Ordnung sein, aber für andere müssen Sie auf mindestens 16 Bit aufrüsten, die 216=65,5362^16 = 65,536 Zahlen eindeutig darstellen können. 32 Bit unterstützen 232=4.294.967.2962^32 = 4.294.967.296 verschiedene Zahlen. Mit zunehmender Größe des Feldes steigt auch die Anzahl der benötigten Bits. Um NN verschiedene Zahlen eindeutig darzustellen, braucht man k≥log2Nk \geq \log_2{N}. Wenn Sie also nicht mit vielen Duplikaten in Ihrem Array einverstanden sind, ist O(kN)O(kN) effektiv O(NlogN)O(N\log{N}).
Die Notwendigkeit von O(NlogN)O(N\log{N}) an Eingabedaten im allgemeinen Fall beweist eigentlich das Gesamtergebnis von selbst. Dieses Argument ist in der Praxis nicht so interessant, weil wir selten Milliarden von ganzen Zahlen auf einer 32-Bit-Maschine sortieren müssen, und wenn jemand an die Grenzen einer 64-Bit-Maschine gestoßen ist, hat er es uns nicht gesagt.