Sorteer op vergelijking
| n | log log 2 (n ! )⌉ {\displaystyle \ left \lceil \ 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 of 46 |
| 17 | 49 | 49 of 50 |
| 18 | 53 | 53 of 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | log log 2 (n ! )⌉ {\displaystyle \ left \lceil \ log _ {2} (n!) \ right \ rceil }
|
n log 2 n − n ln 2 {\displaystyle\n \ log _{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 |
tot het werkelijke minimum aantal vergelijkingen (van OEIS: A036604) dat nodig is om een lijst van n items te sorteren (voor het slechtste geval). Hieronder: met behulp van Stirling ‘ s benadering wordt deze ondergrens goed benaderd door n log 2 n-n ln 2 2 {\displaystyle n \ log _{2}n – {\frac {n} {\ln 2}}}
.
het aantal vergelijkingen dat een vergelijkingssorteeralgoritme nodig heeft neemt toe in verhouding tot n log ( n ) {\displaystyle n\log(n))}
, waarbij n {\displaystyle n}
is het aantal elementen om te sorteren. Deze binding is asymptotisch strak.
gegeven een lijst van verschillende getallen (we kunnen dit aannemen omdat dit een worst-case analyse is), zijn er n factoriële permutaties precies een daarvan is de lijst in gesorteerde volgorde. Het sorteeralgoritme moet voldoende informatie uit de vergelijkingen verzamelen om de juiste permutatie te identificeren. Als het algoritme altijd voltooit na ten hoogste f(n) stappen, kan het niet meer dan 2F (n) gevallen onderscheiden omdat de sleutels verschillend zijn en elke vergelijking slechts twee mogelijke uitkomsten heeft. Daarom
2 f (n ) ≥ n ! {\displaystyle 2^{f (n)} \ geq n!}
, of equivalent f (n ) ≥ log 2 (n ! ) . {\displaystyle f (n) \geq \ log _{2}(n!).}
door te kijken naar de eerste n / 2 {\displaystyle n/2}
factoren van n ! = n (n − 1 ) ⋯ 1 {\displaystyle n!=n (n-1) \ cdots 1}
, krijgen we log 2 (n ! ) ≥ log 2 ((n 2) n 2) = N 2 log n n log 2 2 − n 2 = Θ ( n log n n). {\displaystyle \ log _{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 \ log _{2} (n!) = \Omega (n \ log n).}
dit vormt het ondergrens van de vordering. Een betere binding kan worden gegeven via Stirling ‘ s benadering.
een identieke bovengrens volgt uit het bestaan van de algoritmen die deze grens in het slechtste geval bereiken, zoals heapsort en mergesort.
het bovenstaande argument geeft een absolute, in plaats van alleen asymptotische ondergrens op het aantal vergelijkingen, namelijk ⌈ log 2 (n ! )⌉ {\displaystyle \ left \lceil \ log _ {2} (n!) \ right \ rceil }
vergelijkingen. Deze ondergrens is redelijk goed (het kan worden benaderd binnen een lineaire tolerantie door een eenvoudige merge sort), maar het is bekend dat het onnauwkeurig is. Bijvoorbeeld, log log 2 (13 ! )⌉ = 33 {\displaystyle \ left \lceil \ log _ {2} (13!) \ right \ rceil =33}
, maar het minimale aantal vergelijkingen om 13 elementen te sorteren is bewezen 34 te zijn.
het bepalen van het exacte aantal vergelijkingen dat nodig is om een bepaald aantal items te sorteren is een rekenkundig moeilijk probleem, zelfs voor kleine n, en er is geen eenvoudige formule voor de oplossing bekend. Voor enkele van de weinige concrete waarden die zijn berekend, zie OEIS: A036604.
ondergrens voor het gemiddelde aantal vergelijkingenwaarde
een soortgelijke grens geldt voor het gemiddelde aantal vergelijkingen. Aangenomen dat
- alle sleutels verschillend zijn, dat wil zeggen dat elke vergelijking een>b of een<b oplevert, en
- de invoer een willekeurige permutatie is, uniform gekozen uit de verzameling van alle mogelijke permutaties van n elementen,
het is onmogelijk om te bepalen in welke volgorde de invoer zich bevindt met minder dan log2 (n!) vergelijkingen gemiddeld.
dit is het gemakkelijkst te zien aan de hand van concepten uit de informatietheorie. De Shannon entropie van zo ‘ n willekeurige permutatie is log2(n!) bit. Aangezien een vergelijking slechts twee resultaten kan opleveren, is de maximale hoeveelheid informatie die het levert 1 bit. Daarom is na K vergelijkingen de resterende entropie van de permutatie, gegeven de resultaten van die vergelijkingen, ten minste log2(n!)- k bits gemiddeld. Om de sortering uit te voeren, is volledige informatie nodig, dus de resterende entropie moet 0 zijn. Hieruit volgt dat k minstens log2 (n!) gemiddeld.
de ondergrens afgeleid via de informatietheorie wordt geformuleerd als ‘informatietheoretische ondergrens’. Informatietheoretische ondergrens is correct, maar is niet noodzakelijk de sterkste ondergrens. En in sommige gevallen kan de informatietheoretische ondergrens van een probleem zelfs ver van de ware ondergrens liggen. Bijvoorbeeld, de informatie-theoretische ondergrens van de selectie is ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
terwijl n − 1 {\displaystyle n-1}
vergelijkingen nodig zijn voor een adversarial argument. Het samenspel tussen informatietheoretische ondergrens en de ware ondergrens lijkt veel op een reëel-gewaardeerde functie die een integer functie met een lagere begrenzing begrenst. Dit is echter niet precies juist wanneer het gemiddelde geval wordt bekeken.
om te achterhalen wat er gebeurt bij het analyseren van het gemiddelde geval, is de sleutel dat waar ‘gemiddeld’ naar verwijst? Gemiddeld waarover? Met enige kennis van de informatietheorie, de informatietheorie ondergrens gemiddelden over de verzameling van alle permutaties als een geheel. Maar om het even welke computeralgoritmen (onder wat momenteel wordt verondersteld) moeten elke permutatie als een individuele instantie van het probleem behandelen. Vandaar dat de gemiddelde ondergrens die we zoeken gemiddeld is over alle individuele gevallen.
om te zoeken naar de ondergrens met betrekking tot de niet-haalbaarheid van computers, gebruiken we het Beslissingsboommodel. Laten we een beetje anders formuleren wat ons doel is. In het Beslissingsboommodel is de ondergrens die getoond moet worden de ondergrens van de gemiddelde lengte van wortel-tot-blad paden van een n ! {\displaystyle n!}
– bladbinaire boom (waarbij elk blad overeenkomt met een permutatie). Men zou ervan overtuigd zijn te zeggen dat een gebalanceerde volledige binaire boom het minimum van de gemiddelde lengte bereikt. Met een aantal zorgvuldige berekeningen, voor een evenwichtige volledige binaire boom met n ! {\displaystyle n!}
bladeren, de gemiddelde lengte van wortel-tot-blad paden wordt gegeven door (2 n ! – 2 log log 2 n ! ⌋ + 1) log log 2 n ! ⌉ + (2 log log 2 n ! ⌋ + 1-n ! ) log log 2 n ! ⌋ n ! {\displaystyle {\frac {(2n!-2^{\lfloor \ log _{2}n!\rfloor +1})\cdot \lceil \log _{2}n!\rceil +(2^{\lfloor \ log _{2}n!\rfloor + 1} – n!) \cdot \ lfloor \ log _{2}n!\rfloor} {n!}}}
bijvoorbeeld, voor n = 3 is de informatietheoretische ondergrens voor het gemiddelde geval ongeveer 2,58, terwijl de gemiddelde ondergrens afgeleid via Beslissingsboommodel 8/3 is, ongeveer 2,67.
in het geval dat meerdere posten dezelfde sleutel kunnen hebben, is er geen duidelijke statistische interpretatie voor de term “gemiddeld geval”, zodat een argument als het bovenstaande niet kan worden toegepast zonder specifieke aannames te maken over de verdeling van sleutels.
