Összehasonlítás rendezés
| n | 6. napló (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 vagy 46 |
| 17 | 49 | 49 vagy 50 |
| 18 | 53 | 53 vagy 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | 6. napló (n ! ) {\displaystyle \ left \ lceil \log _ {2} (n!)\right \ rceil }
|
n log 2 (n − n ln) 2 (n) {\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 |
az összehasonlítások tényleges minimális számához (az OEIS-től: A036604), amely az n elemek listájának rendezéséhez szükséges (a legrosszabb esetben). Lent: Stirling közelítésével ezt az alsó határt jól közelítjük n log 2 − vel (n-n ln) (2) {\displaystyle n\log _{2}n – {\frac {n}{\ln) 2}}}
.
az összehasonlítások száma, amelyeket egy összehasonlító rendezési algoritmus igényel, n log ( n ) {\displaystyle n\log (n)}
, ahol n {\displaystyle n}
a rendezendő elemek száma. Ez a kötés aszimptotikusan szoros.
adott egy listát a különböző számok (feltételezhetjük ezt, mert ez egy legrosszabb esetben elemzés), vannak n faktoriális permutációk pontosan amelyek közül az egyik a lista rendezve. A rendezési algoritmusnak elegendő információt kell szereznie az összehasonlításokból a helyes permutáció azonosításához. Ha az algoritmus mindig legfeljebb f(n) lépés után fejeződik be, akkor nem tud 2F(n) – nél több esetet megkülönböztetni, mert a kulcsok különböznek egymástól, és minden összehasonlításnak csak két lehetséges eredménye van. Ezért
2 f (n) n ! {\displaystyle 2^{f (n)} \ geq n!}
, vagy ekvivalens módon f ( n)! ) . {\displaystyle f (n) \geq \ log _{2}(n!).}
az első n / 2 {\displaystyle n/2}
tényezők n ! = n (n − 1) 6 {\displaystyle n!=n (n-1)\cdots 1}
, megkapjuk log 2 ( 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} \ 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).}
napló 2 ! ) = (N log = n). {\displaystyle \ log _ {2}(n!) = \ Omega (n\log n).}
ez biztosítja a követelés alsó határát. Egy jobb kötött adható keresztül Stirling közelítése.
azonos felső határ következik az algoritmusok létezéséből, amelyek a legrosszabb esetben elérik ezt a határt, mint például a heapsort és a mergesort.
a fenti argumentum abszolút értéket ad, nem csak aszimptotikus alsó korlátot az összehasonlítások számára, nevezetesen a 2. naplójú ( n ! ) {\displaystyle \ left \ lceil \log _ {2} (n!) \ right \ rceil }
összehasonlítások. Ez az alsó határ meglehetősen jó (lineáris tolerancián belül egyszerű egyesítési rendezéssel lehet megközelíteni), de ismert, hogy pontatlan. Például, ha valaki naplózza a 2 ( 13 ! ) 63 {\displaystyle \left\lceil \log _{2} (13!) \ right \ rceil =33}
, de a 13 elem rendezésére vonatkozó összehasonlítások minimális száma 34-nek bizonyult.
az adott számú bejegyzés rendezéséhez szükséges összehasonlítások pontos számának meghatározása számítási szempontból nehéz probléma még kis n esetén is, és a megoldásra nem ismert egyszerű képlet. A kiszámított néhány konkrét értékről lásd: OEIS: A036604.
az összehasonlítások átlagos számának alsó korlátja
hasonló korlátozás vonatkozik az összehasonlítások átlagos számára. Feltételezve, hogy
- az összes kulcs megkülönböztethető, azaz minden összehasonlítás vagy a>b vagy a< b értéket ad, és
- a bemenet véletlenszerű permutáció, amelyet egyenletesen választanak ki az összes lehetséges permutáció halmazából n elemek,
lehetetlen meghatározni, hogy melyik sorrendben van a bemenet kevesebb, mint log2 (n!) összehasonlítások átlagosan.
ez a legkönnyebben az információelmélet fogalmainak felhasználásával látható. Egy ilyen véletlenszerű permutáció Shannon-entrópiája log2 (n!) bitek. Mivel az összehasonlítás csak két eredményt adhat, az általa nyújtott információk maximális mennyisége 1 bit. Ezért k összehasonlítások után a permutáció fennmaradó entrópiája, figyelembe véve ezen összehasonlítások eredményeit, legalább log2 (n!)- K bit átlagosan. A rendezés végrehajtásához teljes információra van szükség, tehát a fennmaradó entrópiának 0-nak kell lennie. Ebből következik, hogy k legalább log2 (n!) átlagosan.
az információelméletből levezetett alsó korlátot ‘információelméleti alsó korlátnak’nevezik. Az információelméleti alsó határ helyes, de nem feltétlenül a legerősebb alsó határ. Bizonyos esetekben a probléma információelméleti alsó határa még messze is lehet a valódi alsó korláttól. Például a szelekció információelméleti alsó határa: \ log 2 = \ log (n) \ {\displaystyle \ left\lceil \ log _ {2}(n) \ right \ rceil_ }
míg N − 1 {\displaystyle n-1}
az összehasonlításokat kontradiktórius érveléssel kell elvégezni. Az információelméleti alsó határ és a valódi alsó határ közötti kölcsönhatás nagyon hasonlít egy valós értékű függvényhez, amely egy egész függvényt határol. Ez azonban nem pontosan helyes, ha az átlagos esetet vesszük figyelembe.
annak feltárásához, hogy mi történik az átlagos eset elemzése során, a legfontosabb az, hogy mire utal az ‘átlag’? Átlagolni mit? Az információelmélet bizonyos ismereteivel az információelméleti alsó határ átlaga az összes permutáció egészének halmazán. De minden számítógépes algoritmusnak (a jelenleg vélteknek megfelelően) minden permutációt a probléma egyedi példányaként kell kezelnie. Ezért az átlagos alsó határ, amelyet keresünk, az összes egyedi esetre átlagolva van.
a számítógépek elérhetetlenségére vonatkozó alsó határ kereséséhez a döntési fa modellt alkalmazzuk. Fogalmazzunk meg egy kicsit arról, hogy mi a célunk. A döntési fa modellben a bemutatandó alsó határ az n gyökér-levél útjainak átlagos hosszának alsó határa ! {\displaystyle n!}
– levél bináris fa (amelyben minden levél egy permutációnak felel meg). Meg lenne győződve arról, hogy egy kiegyensúlyozott teljes bináris fa eléri az átlagos hosszúság minimumát. Néhány gondos számítások, a kiegyensúlyozott teljes bináris fa n ! {\displaystyle n!}
levelek, a gyökér-levél utak átlagos hosszát ( 2 n ! – 2 db. napló 2 db. n ! ~ + 1) ~ napló 2 ~ n ! ~ + (2 ~ napló 2 ~ n ! + 1 − n ! ) 6. napló n ! 6 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!}}}
például N = 3 esetén az átlagos eset információelméleti alsó határa körülbelül 2,58, míg a döntési fa modellen keresztül levezetett átlagos alsó határ 8/3, körülbelül 2,67.
abban az esetben, ha több elemnek lehet ugyanaz a kulcsa, nincs nyilvánvaló statisztikai értelmezés az “átlagos eset” kifejezésre, ezért a fenti érv nem alkalmazható anélkül, hogy konkrét feltételezéseket tennénk a kulcsok eloszlásáról.
