Vergleich sortieren
| n | ⌈ log 2 ( n ! ) ⌉ {\displaystyle \left\lc } \log _{2}(n!)\right\rceil }
 |
Minimum |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 oder 46 |
| 17 | 49 | 49 oder 50 |
| 18 | 53 | 53 oder 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ log 2 ( n ! ) ⌉ {\displaystyle \left\lc } \log _{2}(n!)\right\rceil }
|
n logarithmisch 2 n – n ln 2 {\displaystyle n\logarithmisch _{2}n-{\frac {n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
auf die tatsächliche Mindestanzahl von Vergleichen (aus OEIS: A036604), die zum Sortieren einer Liste von n Elementen erforderlich sind (für den schlimmsten Fall). Unten: Mit Stirlings Approximation wird diese untere Grenze gut angenähert durch n log 2 n – n ln 2 {\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
.
Die Anzahl der Vergleiche, die ein Vergleichssortieralgorithmus benötigt, steigt proportional zu n log (n ) {\displaystyle n\log(n)}
, wobei n {\displaystyle n}
ist die Anzahl der zu sortierenden Elemente. Diese Grenze ist asymptotisch eng.
Bei einer Liste verschiedener Zahlen (wir können davon ausgehen, dass dies eine Worst-Case-Analyse ist) gibt es n Fakultätspermutationen, von denen genau eine die Liste in sortierter Reihenfolge ist. Der Sortieralgorithmus muss genügend Informationen aus den Vergleichen gewinnen, um die richtige Permutation zu identifizieren. Wenn der Algorithmus immer nach höchstens f (n) Schritten abgeschlossen ist, kann er nicht mehr als 2f (n) Fälle unterscheiden, da die Schlüssel unterschiedlich sind und jeder Vergleich nur zwei mögliche Ergebnisse hat. Daher
2 f ( n ) ≥ n ! {\displaystyle 2^{f(n)}\geq n!}
oder äquivalent f ( n ) ≥ log 2 ( n ! ) . {\displaystyle f(n)\geq \log _{2}(n!).}
Durch Betrachtung des ersten n / 2 {\displaystyle n/2}
Faktoren von n ! = n ( n − 1 ) ⋯ 1 {\displaystyle n!=n(n-1)\cdots 1}
, erhalten wir log 2 ( n ! ) ≥ log 2 ( ( n 2 ) n 2 ) = n 2 log n log 2 − n 2 = Θ ( n log n ) . {\displaystyle \logarithmisch _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}
log 2 ( n ! ) = Ω ( n log n ) . {\displaystyle \logarithmisch _{2}(n!)=\Omega (n\log n).}
Dies stellt den untergeordneten Teil des Anspruchs bereit. Eine bessere Grenze kann über Stirlings Approximation gegeben werden.
Eine identische Obergrenze ergibt sich aus der Existenz der Algorithmen, die diese Grenze im schlimmsten Fall erreichen, wie Heapsort und mergesort.
Das obige Argument liefert eine absolute und nicht nur asymptotische Untergrenze für die Anzahl der Vergleiche, nämlich ⌈ log 2 ( n ! ) ⌉ {\displaystyle \left\lc } \log _{2}(n!)\right\rceil }
Vergleiche. Diese untere Grenze ist ziemlich gut (sie kann innerhalb einer linearen Toleranz durch eine einfache Zusammenführungssortierung angefahren werden), aber es ist bekannt, dass sie ungenau ist. Zum Beispiel ⌈ log 2 ( 13 ! ) ⌉ = 33 {\displaystyle \left\lc } \log _{2}(13!)\right\rceil =33}
, die minimale Anzahl von Vergleichen zum Sortieren von 13 Elementen hat sich jedoch als 34 erwiesen.
Das Bestimmen der genauen Anzahl von Vergleichen, die zum Sortieren einer bestimmten Anzahl von Einträgen erforderlich sind, ist selbst für kleine n ein rechenintensives Problem, und es ist keine einfache Formel für die Lösung bekannt. Einige der wenigen konkreten Werte, die berechnet wurden, finden Sie unter OEIS: A036604.
Untere Grenze für die durchschnittliche Anzahl von Vergleichenbearbeiten
Eine ähnliche Grenze gilt für die durchschnittliche Anzahl von Vergleichen. Angenommen,
- Alle Schlüssel sind verschieden, dh jeder Vergleich ergibt entweder a> b oder a< b und
- Die Eingabe ist eine zufällige Permutation, die einheitlich aus der Menge aller möglichen Permutationen von n Elementen ausgewählt wird,
es ist unmöglich zu bestimmen, in welcher Reihenfolge sich die Eingabe mit weniger als log2(n!) vergleiche im Durchschnitt.
Dies kann am einfachsten anhand von Konzepten aus der Informationstheorie gesehen werden. Die Shannon-Entropie einer solchen zufälligen Permutation ist log2 (n!) bisschen. Da ein Vergleich nur zwei Ergebnisse liefern kann, beträgt die maximale Informationsmenge 1 Bit. Daher ist nach k Vergleichen die verbleibende Entropie der Permutation angesichts der Ergebnisse dieser Vergleiche mindestens log2 (n!) – k Bits im Durchschnitt. Um die Sortierung durchzuführen, werden vollständige Informationen benötigt, daher muss die verbleibende Entropie 0 sein. Daraus folgt, dass k mindestens log2(n!) durchschnittlich.
Die über die Informationstheorie abgeleitete Untergrenze wird als ‘informationstheoretische Untergrenze’ formuliert. Die informationstheoretische Untergrenze ist korrekt, aber nicht unbedingt die stärkste Untergrenze. Und in einigen Fällen kann die informationstheoretische Untergrenze eines Problems sogar weit von der wahren Untergrenze entfernt sein. Zum Beispiel ist die informationstheoretische untere Grenze der Selektion ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
während n − 1 {\displaystyle n-1}
Vergleiche durch ein kontradiktorisches Argument benötigt werden. Das Zusammenspiel zwischen informationstheoretischer Untergrenze und der wahren Untergrenze ähnelt einer reellwertigen Funktion, die eine ganzzahlige Funktion tiefer begrenzt. Dies ist jedoch nicht genau richtig, wenn der durchschnittliche Fall betrachtet wird.
Um herauszufinden, was bei der Analyse des Durchschnittsfalls passiert, lautet der Schlüssel: Worauf bezieht sich ‘Durchschnitt’? Mittelwertbildung über was? Mit einigen Kenntnissen der Informationstheorie mittelt die informationstheoretische Untergrenze über die Menge aller Permutationen als Ganzes. Aber alle Computeralgorithmen (nach dem, was derzeit angenommen wird) müssen jede Permutation als eine einzelne Instanz des Problems behandeln. Daher wird die durchschnittliche untere Grenze, nach der wir suchen, über alle Einzelfälle gemittelt.
Um nach der unteren Grenze der Nicht Erreichbarkeit von Computern zu suchen, verwenden wir das Entscheidungsbaummodell. Lassen Sie uns ein wenig umformulieren, was unser Ziel ist. Im Entscheidungsbaummodell ist die darzustellende Untergrenze die Untergrenze der durchschnittlichen Länge der Wurzel-zu-Blatt-Pfade eines n ! {\displaystyle n!}
-Blattbinärbaum (in dem jedes Blatt einer Permutation entspricht). Es wäre überzeugend zu sagen, dass ein ausgewogener vollständiger Binärbaum das Minimum der durchschnittlichen Länge erreicht. Mit einigen sorgfältigen Berechnungen für einen ausgeglichenen vollständigen Binärbaum mit n ! {\displaystyle n!}
Blätter, die durchschnittliche Länge der Wurzel-zu-Blatt-Pfade ist gegeben durch ( 2 n ! – 2 log log 2 n ! ⌋ + 1 ) ⋅ log log 2 n ! ⌉ + ( 2 log log 2 n ! ⌋ + 1 – n ! ) ⋅ ⌊ log 2 n ! ⌋ n ! {\displaystyle {\frac {(2n!-2^{\l} \log _{2}n!\rfloor +1})\cdot \lceil \log _{2}n!\rceil +(2^{\l } \log _{2}n!\r { +1}-n!)\cdot \lfloor \log _{2}n!\rfloor }{n!}}}
Beispielsweise beträgt für n = 3 die informationstheoretische Untergrenze für den durchschnittlichen Fall ungefähr 2,58, während die über das Entscheidungsbaummodell abgeleitete durchschnittliche Untergrenze 8/3 beträgt, ungefähr 2,67.
Für den Fall, dass mehrere Elemente denselben Schlüssel haben können, gibt es keine offensichtliche statistische Interpretation für den Begriff “durchschnittlicher Fall”, so dass ein Argument wie das obige nicht angewendet werden kann, ohne spezifische Annahmen über die Verteilung der Schlüssel zu treffen.
