Sammenligning sort
| n | Hr. log 2 Hr. ( 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 eller 46 |
| 17 | 49 | 49 eller 50 |
| 18 | 53 | 53 eller 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | Hr. log 2 Hr. ( 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 |
til det faktiske mindste antal sammenligninger (fra OEIS: A036604), der kræves for at sortere en liste over n-emner (i værste fald). Nedenfor: ved hjælp af Stirlings tilnærmelse er denne nedre grænse godt tilnærmet af n log 2 list n – n ln list 2 {\displaystyle n \ log _{2}n – {\frac {n} {\ln 2}}}
.
antallet af sammenligninger, som en sammenligningssorteringsalgoritme kræver, stiger i forhold til n-log-Larsen (n) {\displaystyle n \ – log (n)}
, hvor n {\displaystyle n}
er antallet af elementer, der skal sorteres. Denne grænse er asymptotisk stram.
givet en liste over forskellige tal (vi kan antage dette, fordi dette er en værst tænkelig analyse), er der n faktorielle permutationer, hvoraf den ene er listen i sorteret rækkefølge. Sorteringsalgoritmen skal få nok information fra sammenligningerne til at identificere den korrekte permutation. Hvis algoritmen altid afsluttes efter højst f(n) trin, kan den ikke skelne mere end 2F (n) tilfælde, fordi tasterne er forskellige, og hver sammenligning har kun to mulige resultater. Derfor
2 f (n) Hr. n ! {\displaystyle 2^{f (n)}\søg n!}
, eller ækvivalent f ( n) lot log 2 lot ( n ! ) . {\displaystyle f (n) \søg \ log _{2}(n!).}
ved at se på den første n / 2 {\displaystyle n/2}
faktorer af n ! = n (n − 1) 1 {\displaystyle n!=n (n-1)\cdots 1}
, vi får log 2 liter ( n ! ) ≥ log 2 ( ( n-2 ) n-2 ) = n 2 log n log 2 − n 2 = Θ ( n log n ) . {\displaystyle \ log _{2} (n!) \ frac \ log _{2} \ venstre (\venstre ({\frac {n}{2}}\højre)^{\frac {n}{2}}\højre)={\frac {n}{2}} {\frac {\log n} {\log 2}}-{\frac {n}{2}}=\Theta (n \ log n).}
log 2 LP (n ! ) = Kr. (n log kr . {\displaystyle \ log _{2} (n!) =\Omega (n\log n).}
dette giver den nederste del af kravet. En bedre bundet kan gives via Stirlings tilnærmelse.
en identisk øvre grænse følger af eksistensen af de algoritmer, der opnår denne grænse i værste fald, som heapsort og mergesort.
ovenstående argument giver en absolut, snarere end kun asymptotisk nedre grænse for antallet af sammenligninger, nemlig LR log 2 LRR ( n ! ) {\displaystyle \ left \ lceil \ log _{2} (n!) \ right \ rceil }
sammenligninger. Denne nedre grænse er ret god (den kan næres inden for en lineær tolerance ved en simpel fletningssortering), men det vides at være upræcis. For eksempel log log 2 ( 13 ! ) = 33 {\displaystyle \ left \ lceil \ log _{2} (13!) \ right \ rceil =33}
, men det minimale antal sammenligninger til at sortere 13 elementer har vist sig at være 34.
at bestemme det nøjagtige antal sammenligninger, der er nødvendige for at sortere et givet antal poster, er et beregningsmæssigt hårdt problem, selv for små n, og ingen simpel formel til løsningen er kendt. For nogle af de få konkrete værdier, der er beregnet, se OEIS: a036604.
nedre grænse for det gennemsnitlige antal sammenligninger
en tilsvarende grænse gælder for det gennemsnitlige antal sammenligninger. Forudsat at
- alle nøgler er forskellige, dvs. hver sammenligning vil give enten en>b eller en< b og
- input er en tilfældig permutation, valgt ensartet fra sættet af alle mulige permutationer af N elementer,
det er umuligt at afgøre, hvilken rækkefølge input er i med færre end log2 (n!) sammenligninger i gennemsnit.
dette kan lettest ses ved hjælp af begreber fra informationsteori. Shannon-entropien af en sådan tilfældig permutation er log2 (n!) bit. Da en sammenligning kun kan give to resultater, er den maksimale mængde information, den giver, 1 bit. Derfor, efter K sammenligninger den resterende entropi af permutationen, givet resultaterne af disse sammenligninger, er mindst log2(n!)- k bits i gennemsnit. For at udføre sorteringen er der brug for komplette oplysninger, så den resterende entropi skal være 0. Det følger heraf, at k skal være mindst log2 (n!) i gennemsnit.
den nedre grænse afledt via informationsteori er formuleret som ‘informationsteoretisk nedre grænse’. Informationsteoretisk nedre grænse er korrekt, men er ikke nødvendigvis den stærkeste nedre grænse. Og i nogle tilfælde kan den informationsteoretiske nedre grænse for et problem endda være langt fra den sande nedre grænse. For eksempel er den informationsteoretiske nedre grænse for udvælgelse en logbog 2 en logbog (n) en log {\displaystyle \ left \ lceil \ log _ {2} (n) en ret\rceil }
mens n − 1 {\displaystyle n-1}
sammenligninger er nødvendige af et kontradiktorisk argument. Samspillet mellem informationsteoretisk nedre grænse og den sande nedre grænse er meget som en virkelig værdsat funktion, der afgrænser en heltalsfunktion. Dette er dog ikke helt korrekt, når den gennemsnitlige sag overvejes.
for at finde ud af, hvad der sker, mens man analyserer den gennemsnitlige sag, er nøglen, at hvad henviser ‘gennemsnit’ til? Gennemsnit over hvad? Med en vis viden om informationsteori er den informationsteoretiske nedre grænse gennemsnit over sættet af alle permutationer som helhed. Men enhver computeralgoritme (under hvad der menes i øjeblikket) skal behandle hver permutation som en individuel forekomst af problemet. Derfor er den gennemsnitlige nedre grænse, Vi søger efter, gennemsnitlig over alle individuelle tilfælde.
for at søge efter den nedre grænse, der vedrører computerens manglende opnåelighed, vedtager vi Beslutningstræmodellen. Lad os omformulere lidt af, hvad vores mål er. I Beslutningstræmodellen, den nedre grænse, der skal vises, er den nedre grænse for den gennemsnitlige længde af rod-til-bladstier i en n ! {\displaystyle n!}
– blad binært træ (hvor hvert blad svarer til en permutation). Det ville være overbevist om at sige, at et afbalanceret fuldt binært træ opnår minimum af gennemsnitslængden. Med nogle omhyggelige beregninger, for en afbalanceret fuld binært træ med n ! {\displaystyle n!}
blade, den gennemsnitlige længde af rod-til-blad stier er givet af ( 2 n ! – 2 LP log 2 LP n ! Kr + 1) kr 2 kr ! Kr + (2 kr log 2 kr ! LR + 1 – n ! ) lænd log 2 lænd n ! løjtnant 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!}}}
for eksempel for n = 3 er den informationsteoretiske nedre grænse for det gennemsnitlige tilfælde cirka 2,58, mens den gennemsnitlige nedre grænse afledt via Beslutningstræmodel er 8/3, cirka 2,67.
i tilfælde af at flere poster kan have den samme nøgle, er der ingen åbenbar statistisk fortolkning for udtrykket “gennemsnitlig sag”, så et argument som ovenstående kan ikke anvendes uden at tage specifikke antagelser om fordelingen af nøgler.
