Sammenligning sorter
| n | ⌈ logg inn 2 (n ! )⌉ {\displaystyle \ venstre \ lceil \log _ {2} (n!) \ høyre \ 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 | ⌈ logg inn 2 (n ! )⌉ {\displaystyle \ venstre \ lceil \log _ {2} (n!) \ høyre \ rceil }
|
n logg 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 minimum antall sammenligninger (FRA OEIS: A036604) som kreves for å sortere en liste over n elementer (i verste fall). Under: Ved Å bruke Stirlings tilnærming er denne nedre grensen godt tilnærmet med n logg 2 n-n ln 2 {\displaystyle n\log _{2}n – {\frac {n}{\ln 2}}}
.
antallet sammenligninger som en sammenligningssorteringsalgoritme krever øker i forhold til n log (n ) {\displaystyle n\log (n)}
, hvor n {\displaystyle n}
er antall elementer som skal sorteres. Denne grensen er asymptotisk tett.
Gitt en liste over forskjellige tall (vi kan anta dette fordi dette er en worst case-analyse), er det n faktorielle permutasjoner, hvorav en er listen i sortert rekkefølge. Sorteringsalgoritmen må få nok informasjon fra sammenligningene for å identifisere riktig permutasjon. Hvis algoritmen alltid fullfører etter maksimalt f (n) trinn, kan den ikke skille mer enn 2f (n) tilfeller fordi tastene er forskjellige og hver sammenligning har bare to mulige utfall. Derfor
2 f (n ) ≥ n ! {\displaystyle 2^{f (n)} \ geq n!}
, eller tilsvarende f (n) ≥ logg 2 (n! ) . {\displaystyle f (n) \geq \ log _{2}(n!).}
ved å se på den første n / 2 {\displaystyle n/2}
faktorer av n ! = n ( n − 1 ) ⋯ 1 {\displaystyle n!= n (n-1) \ cdots 1}
, får vi logg 2 (n ! ) ≥ logg 2 ( ( n-2 ) n-2 ) = n 2 logg n logg 2 − n 2 = Θ ( n log n ) . {\displaystyle \ log _{2}(n!) \ geq \ log _{2}\venstre (\venstre ({\frac {n}{2}} \ høyre)^{\frac {n}{2}}\høyre) = {\frac {n}{2}} {\frac {\log n} {\log 2}} – {\frac {n}{2}}=\Theta (n\log n).}
logg 2 (n ! ) = Ω (n logg n ) . {\displaystyle \ log _{2}(n!) = \ Omega (n \ log n).}
Dette gir den nedre delen av kravet. En bedre bundet kan gis via Stirlings tiln rming.
en identisk øvre grense følger av eksistensen av algoritmer som oppnår denne bundet i verste fall, som heapsort og mergesort.
argumentet ovenfor gir en absolutt, snarere enn bare asymptotisk nedre grense på antall sammenligninger, nemlig ⌈ log 2 (n ! )⌉ {\displaystyle \ venstre \ lceil \log _ {2} (n!) \ right \ rceil }
sammenligninger. Denne nedre grensen er ganske god (den kan nærmer seg innenfor en lineær toleranse ved en enkel fusjonsortering), men det er kjent å være inexakt. For eksempel, ⌈ logg 2 (13 ! )⌉ = 33 {\displaystyle \ venstre \ lceil \log _{2} (13!) \ right \ rceil =33}
, men det minimale antall sammenligninger for å sortere 13 elementer har vist seg å være 34.
Å Bestemme det nøyaktige antall sammenligninger som trengs for å sortere et gitt antall oppføringer er et beregningsmessig vanskelig problem selv for liten n, og ingen enkel formel for løsningen er kjent. FOR noen av de få konkrete verdiene som er beregnet, se OEIS: A036604.
Nedre grense for gjennomsnittlig antall sammenligningerrediger
En tilsvarende grense gjelder for gjennomsnittlig antall sammenligninger. Forutsatt at
- alle nøkler er forskjellige, dvs. hver sammenligning vil gi enten a > b eller a < b, og
- inngangen er en tilfeldig permutasjon, valgt jevnt fra settet av alle mulige permutasjoner av n-elementer,
det er umulig å bestemme hvilken rekkefølge inngangen er i med færre enn log2 (n!) sammenligninger i gjennomsnitt.
dette kan lettest ses ved hjelp av begreper fra informasjonsteori. Shannon entropi av en slik tilfeldig permutasjon er log2(n!) bit. Siden en sammenligning bare kan gi to resultater, er den maksimale mengden informasjon den gir 1 bit. Derfor, etter k sammenligninger gjenværende entropi av permutasjon, gitt resultatene av disse sammenligningene, er minst log2 (n!)- k biter i gjennomsnitt. For å utføre sorteringen, er fullstendig informasjon nødvendig, så gjenværende entropi må være 0. Det følger at k må være minst log2 (n!) i gjennomsnitt.
den nedre grensen avledet via informasjonsteori er formulert som ‘informasjonsteoretisk nedre grense’. Informasjonsteoretisk nedre grense er riktig, men er ikke nødvendigvis den sterkeste nedre grensen. Og i noen tilfeller kan den informasjonsteoretiske nedre grensen til et problem til og med være langt fra den sanne nedre grensen. For eksempel er den informasjonsteoretiske nedre grensen til valg ⌈ logg 2 (n)⌉ {\displaystyle \ venstre \ lceil \ log _ {2} (n)\right\rceil }
mens n-1 {\displaystyle n-1}
sammenligninger er nødvendig ved et motsetningsargument. Samspillet mellom informasjonsteoretisk nedre grense og den sanne nedre grensen er mye som en virkelig verdsatt funksjon lavere avgrensning av en heltallsfunksjon. Dette er imidlertid ikke akkurat riktig når gjennomsnittlig sak vurderes.
for å avdekke hva som skjer mens du analyserer gjennomsnittlig sak, er nøkkelen at hva refererer’ gjennomsnitt ‘ til? Gjennomsnitt over hva? Med litt kunnskap om informasjonsteori, informasjonsteoretiske nedre grense gjennomsnitt over settet av alle permutasjoner som helhet. Men noen datalgoritmer (under det som antas for tiden) må behandle hver permutasjon som en individuell forekomst av problemet. Derfor er den gjennomsnittlige nedre grensen vi søker etter i gjennomsnitt over alle enkeltsaker.
for å søke etter den nedre grensen knyttet til datamaskiner som ikke er oppnåelige, vedtar Vi Decision tree-modellen. La oss omformulere litt av hva målet vårt er. I Beslutningstremodellen er den nedre grensen som skal vises, den nedre grensen til den gjennomsnittlige lengden på rot-til-bladbaner av en n ! {\displaystyle n!}
– blad binært tre(hvor hvert blad tilsvarer en permutasjon). Det ville være overbevist om å si at et balansert fullt binært tre oppnår minimum gjennomsnittlig lengde. Med noen forsiktige beregninger, for et balansert fullt binært tre med n ! {\displaystyle n!}
blader, gjennomsnittlig lengde på rot-til-bladbaner er gitt av (2 n ! − 2 ⌊ logg inn 2 hryvnias n ! ⌋ + 1) ⋅ ⌈ logg inn 2 Hryvnja + (2 ⌊ logg inn 2 n ! ⌋ + 1-n ! ) ⋅ ⌊ logg 2 hryvnias 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!}}}
for eksempel, for n = 3, er den informasjonsteoretiske nedre grensen for gjennomsnittlig sak omtrent 2,58, mens den gjennomsnittlige nedre grensen avledet via Beslutningstremodell er 8/3, omtrent 2,67.
i tilfelle at flere elementer kan ha samme nøkkel, er det ingen åpenbar statistisk tolkning for begrepet “gjennomsnittlig sak”, så et argument som ovenfor kan ikke brukes uten å gjøre spesifikke forutsetninger om fordelingen av nøkler.
