Dies ist eine maschinelle Übersetzung; maßgeblich ist die englische Originalfassung. Original lesen
Warum Sortieren nicht schneller werden kann
Das Sortieren von hundert Dingen benötigt mindestens 525 Vergleiche. Nicht mit den Algorithmen von heute. Niemals.
Die meisten Aussagen über Leistung beziehen sich auf ein bestimmtes Programm. Diese hier nicht. Sie besagt, dass kein vergleichsbasierter Sortieralgorithmus – von wem auch immer geschrieben, in welcher Sprache auch immer, auf welcher noch nicht erfundenen Hardware auch immer – hundert Elemente in weniger als 525 Vergleichen sortieren kann.
Das Argument betrachtet zu keinem Zeitpunkt einen Algorithmus.
Zählen Sie die Ziele, nicht die Schritte
Eine Liste von n verschiedenen Elementen kann in n! Reihenfolgen angeordnet werden. Genau eine davon ist sortiert, und bevor man beginnt, hat man keine Ahnung, welche davon man in den Händen hält.
Überlegen Sie nun, was ein Vergleich liefert. Sie fragen, ob a vor b steht, und erhalten als Antwort Ja oder Nein. Ein Bit. Was auch immer Ihr Algorithmus als Nächstes tut, er tut es im Wissen um eine binäre Tatsache mehr als zuvor.
Nach c Vergleichen hat man also c Bits empfangen, und c Bits können höchstens 2c verschiedene Situationen unterscheiden. Um sicher zu identifizieren, mit welcher der n! Anordnungen man begonnen hat, benötigt man
2c ≥ n!, das heißt c ≥ log₂(n!).
Das ist bereits der gesamte Beweis. Er enthält keine Schleifen, keine Rekursion und keine Annahmen über eine Strategie – genau deshalb gilt er auch für Algorithmen, an die noch niemand gedacht hat.
Der Standardname dafür ist Entscheidungsbaum-Schranke. Stellen Sie sich ein beliebiges vergleichsbasiertes Sortierverfahren als Baum vor: Jeder innere Knoten ist ein Vergleich, jeder Zweig ist eine der beiden Antworten und jedes Blatt ist eine mögliche Anordnung. Ein Baum der Tiefe c hat höchstens 2c Blätter, und der Baum muss mindestens n! davon besitzen, somit beträgt seine Tiefe mindestens log₂(n!). Die Tiefe entspricht der Anzahl der Vergleiche im schlechtesten Fall.
Wie die Zahlen tatsächlich aussehen
Zwölf Elemente lassen sich auf 479.001.600 Arten anordnen. Der Logarithmus davon beträgt 28,84, folglich benötigen zwölf Elemente mindestens 29 Vergleiche. Hundert Elemente benötigen mindestens 525. Eine Million benötigt mindestens 18.488.885.
Öffnen Sie den Big-O Complexity Explorer und lesen Sie die Zeile für N = 100 ab. Die Spalte O(N log N) zeigt 664, gelegen zwischen O(N) bei 100 und O(N²) bei 10.000. Diese 664 ist N × log₂N, die Wachstumsrate, die wir beim Sortieren als optimal bezeichnen.
Doch die untere Schranke liegt bei 525, und 664 liegt 26,6% darüber.
Diese Lücke ist keine Nachlässigkeit des Werkzeugs. log₂(n!) ist nicht ganz n log₂ n: Die Stirling-Approximation ergibt n log₂ n − 1,4427n, und bei N = 100 macht diese Korrektur 139 Vergleiche aus. „N log N“ benennt also den richtigen Verlauf, überschätzt die tatsächlichen Kosten aber um einen konstanten Faktor der Eingabegröße. Der Verlauf ist das, was bestehen bleibt, wenn N wächst; die 139 ist das, was man bemerken würde, wenn man tatsächlich nachzählen würde.
Der Ausweg, der kein Schlupfloch ist
Counting Sort sortiert eine Million kleiner Ganzzahlen in weit weniger als 18 Millionen Operationen, und das widerspricht keinem einzigen Wort des Obenstehenden.
Der Beweis setzt voraus, dass jede gestellte Frage ein Vergleich ist. Counting Sort stellt eine andere Art von Frage: Es liest einen Schlüssel und nutzt ihn als Adresse. Das gewinnt weit mehr als ein Bit auf einmal, weil es etwas ausnutzt, das das Vergleichsmodell nicht voraussetzen will: nämlich dass die Schlüssel kleine Ganzzahlen sind, in die man hineinschauen darf.
Dies ist die nützliche Erkenntnis. Eine untere Schranke ist immer eine untere Schranke innerhalb eines Modells, und wenn ein Ergebnis unterboten zu werden scheint, wurde das Modell geändert. Sorting Race lässt die vergleichsbasierten Algorithmen gegeneinander antreten, und was sie voneinander trennt, sind konstante Faktoren und das Speicherverhalten, nicht der Exponent. Sie alle sind nach unten durch dieselbe 525 beschränkt.
Wo Ihnen dies bereits begegnet ist
Wenn Ihnen dieser Abzählschritt bekannt vorkommt, ist es genau das Prinzip hinter der Frage, warum kein Komprimierer jede Datei verkleinern kann. Dort ging es um das Zählen möglicher Dateien im Vergleich zu möglichen kürzeren Dateien; hier geht es um mögliche Anordnungen im Vergleich zu möglichen Antwortsequenzen. Beide Beweise funktionieren über die Erkenntnis, dass eine Menge von Ergebnissen größer ist als die Menge der Dinge, die sie beschreiben könnten.
Entropy Coding ist dieselbe Größe aus der anderen Richtung: Die Anzahl der Bits, die Sie tatsächlich benötigen, wird dadurch bestimmt, wie viele Möglichkeiten verbleiben, und keine Kodierung ist besser.
Keines der beiden Ergebnisse verrät Ihnen, wie man ein schnelles Programm schreibt. Sie sagen Ihnen, wann Sie aufhören können, nach einem zu suchen.