Jämförelse Sortera
| n | log 2 ( n ! ) {\displaystyle \left\lceil \log _{2} (n!)\höger \ 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 | log 2 ( n ! ) {\displaystyle \left\lceil \log _{2} (n!)\höger \ rceil }
|
n log 2 (2) (2) (2) (2) (2) (2) (2) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) (n) 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 |
till det faktiska minsta antalet jämförelser (från OEIS: A036604) som krävs för att sortera en lista med n-objekt (i värsta fall). Nedan: med hjälp av Stirlings approximation är denna nedre gräns väl approximerad med n log 2 ACC n − n ln ACC 2 {\displaystyle n \ log _{2}n – {\frac {n} {\ln 2}}}
.
antalet jämförelser som en jämförelsesorteringsalgoritm kräver ökar i proportion till n logg (n) {\displaystyle n \ log (n)}
, där n {\displaystyle n}
är antalet element att sortera. Denna bindning är asymptotiskt tät.
med tanke på en lista med distinkta tal (vi kan anta detta eftersom det här är en värsta fallanalys) finns det n faktoriella permutationer, varav en är listan i sorterad ordning. Sorteringsalgoritmen måste få tillräckligt med information från jämförelserna för att identifiera rätt permutation. Om algoritmen alltid slutförs efter högst f(n) steg kan den inte skilja mer än 2F (n) fall eftersom nycklarna är distinkta och varje jämförelse har bara två möjliga resultat. Därför,
2 f ( n) XXL n ! {\displaystyle 2^{f (n)} \ geq n!}
, eller motsvarande f ( n) 2 oc (n ! ) . {\displaystyle f (n) \geq \ log _{2}(n!).}
genom att titta på den första N / 2 {\displaystyle n/2}
faktorer av n ! = n ( n − 1) 1 {\displaystyle n!= n (n-1)\cdots 1}
, vi får logg 2 msk ( n ! ) ≥ log 2 ( ( n-2 ) n-2 ) = n 2 log n log 2 − n 2 = Θ ( n log n ) . {\displaystyle \ log _ {2} (n!) \geq \ log _{2} \ Vänster (\Vänster ({\frac {n}{2}} \ höger)^{\frac {n}{2}} \ höger)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}} = \Theta (n\log n).}
logga in 2 kg (n ! ) = (. {\displaystyle \ log _ {2} (n!) =\Omega (n \ log n).}
detta ger den nedre bundna delen av fordran. En bättre bunden kan ges via Stirlings approximation.
en identisk övre gräns följer av förekomsten av algoritmerna som uppnår denna gräns i värsta fall, som heapsort och mergesort.
ovanstående argument ger en absolut, snarare än endast asymptotisk nedre gräns för antalet jämförelser, nämligen 2-2-2-2 ( n ! ) {\displaystyle \left\lceil \log _{2} (n!) \ right \ rceil }
jämförelser. Denna nedre gräns är ganska bra (den kan närma sig inom en linjär tolerans med en enkel sammanslagningssort), men den är känd för att vara inexakt. Till exempel, logg 2 oc ( 13 ! ) 63 {\displaystyle \left\lceil \log _{2} (13!) \ right \ rceil =33}
, men det minsta antalet jämförelser för att sortera 13 element har visat sig vara 34.
att bestämma det exakta antalet jämförelser som behövs för att sortera ett visst antal poster är ett beräkningsmässigt svårt problem även för små n, och ingen enkel formel för lösningen är känd. För några av de få konkreta värden som har beräknats, se OEIS: A036604.
nedre gräns för det genomsnittliga antalet jämförelserredigera
en liknande gräns gäller för det genomsnittliga antalet jämförelser. Förutsatt att
- alla tangenter är distinkta, dvs varje jämförelse ger antingen a> b eller A< b och
- ingången är en slumpmässig permutation, vald enhetligt från uppsättningen av alla möjliga permutationer av n-element,
det är omöjligt att bestämma vilken ordning ingången är i med färre än log2 (n! jämförelser i genomsnitt.
detta kan lättast ses med hjälp av begrepp från informationsteori. Shannon entropin av en sådan slumpmässig permutation är log2 (n!) lite. Eftersom en jämförelse bara kan ge två resultat är den maximala informationen 1 bit. Efter k-jämförelser är därför den återstående entropin av permutationen, med tanke på resultaten av dessa jämförelser, åtminstone log2(n!)- k bitar i genomsnitt. För att utföra sorteringen behövs fullständig information, så den återstående entropin måste vara 0. Av detta följer att k måste vara minst log2 (n!) i genomsnitt.
den nedre gränsen härledd via informationsteori formuleras som ‘informationsteoretisk nedre gräns’. Informationsteoretisk nedre gräns är korrekt men är inte nödvändigtvis den starkaste nedre gränsen. Och i vissa fall kan den informationsteoretiska nedre gränsen för ett problem till och med vara långt ifrån den sanna nedre gränsen. Till exempel är den informationsteoretiska nedre gränsen för urvals-log 2 ( n) (2) (2) (n) (2) (n) (n) (n) (n) (n) (n) (n) (n) {\displaystyle \left\lceil \log\{\displaystyle \ Left \ lceil \ log \ {\displaystyle \ Left \ lceil \ log }
medan n − 1 {\displaystyle n-1}
jämförelser behövs av ett kontradiktoriskt argument. Samspelet mellan informationsteoretisk nedre gräns och den sanna nedre gränsen är ungefär som en verklig värderad funktion som begränsar en heltalsfunktion. Detta är dock inte exakt korrekt när det genomsnittliga fallet beaktas.
för att upptäcka vad som händer när man analyserar det genomsnittliga fallet är nyckeln att vad hänvisar’ genomsnitt ‘ till? Medelvärde över vad? Med viss kunskap om informationsteori, den informationsteoretiska nedre gränsen medelvärden över uppsättningen av alla permutationer som helhet. Men alla datoralgoritmer (enligt vad som tros för närvarande) måste behandla varje permutation som en enskild förekomst av problemet. Därför är den genomsnittliga nedre gränsen vi söker i genomsnitt över alla enskilda fall.
för att söka efter den nedre gränsen för datorns icke-uppnåbarhet antar vi Beslutsträdsmodellen. Låt oss omformulera lite av vad vårt mål är. I Beslutsträdsmodellen är den nedre gränsen som ska visas den nedre gränsen för den genomsnittliga längden på rot-till-bladvägar för ett n ! {\displaystyle n!}
– binärt bladträd (där varje blad motsvarar en permutation). Det skulle vara övertygat om att säga att ett balanserat fullt binärt träd uppnår minsta medellängd. Med några noggranna beräkningar, för ett balanserat fullt binärt träd med n ! {\displaystyle n!}
löv, Den genomsnittliga längden på rot-till-bladvägar ges av ( 2 n ! – 2 msk log 2 msk n ! + 1) + 2 + 2 ! + (2-2-2-2-2-2-n ! 2 + 1 − n ! ) 2. 2. 2. n ! ät inte ! {\displaystyle {\frac {(2n!-2^{\lfloor \ log _{2}n!\rfloor + 1})\cdot \lceil \ log _ {2}n!\rceil +(2^{\lfloor \ log _{2}n!\ rgolv + 1} – n!) \ cdot \lfloor \ log _ {2}n!\ rfloor }{n!}}}
till exempel, för n = 3, är den informationsteoretiska nedre gränsen för det genomsnittliga fallet ungefär 2,58, medan den genomsnittliga nedre gränsen härledd via Beslutsträdsmodell är 8/3, ungefär 2,67.
om flera objekt kan ha samma nyckel finns det ingen uppenbar statistisk tolkning för termen “genomsnittligt fall”, så ett argument som ovan kan inte tillämpas utan att göra specifika antaganden om fördelningen av nycklar.
