Srovnání Seřadit
| n | log log 2 (( n ! ) {{\displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil }
 |
Minimální |
|---|---|---|
| 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 nebo 46 |
| 17 | 49 | 49 nebo 50 |
| 18 | 53 | 53 nebo 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ 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 |
skutečné minimální počet srovnání (z OEIS: A036604) nutné, aby třídit seznam položek n (v nejhorším případě). Níže: Pomocí Stirlingova aproximace, tato dolní mez je dobře aproximovat n log 2 n − n ln 2 {\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}
.
počet srovnání, že srovnání sort algoritmus vyžaduje zvyšuje v poměru k n log ( n ) {\displaystyle n\log(n)}
, kde n {\displaystyle n}
je počet prvků třídit. Tato vazba je asymptoticky těsná.
Uveden seznam různých čísel (můžeme předpokládat, že to, protože to je nejhorší-case analýzu), tam jsou n faktoriál, permutace přesně, z nichž jeden je v seznamu seřazeném pořadí. Algoritmus řazení musí získat dostatek informací ze srovnání, aby identifikoval správnou permutaci. Pokud algoritmus vždy dokončí po nanejvýš f(n) kroků, nemůže rozlišit více než 2f(n) případy, protože klíče jsou odlišné a každé srovnání má pouze dva možné výsledky. Proto
2 f (n ) ≥ n ! {\displaystyle 2^{f (n)} \ geq n!}
nebo ekvivalentně f (n ) ≥ log 2 (n ! ) . {\displaystyle f(n)\geq \log _{2} (n!).}
při pohledu na první n / 2 {\displaystyle n/2}
faktory n ! = n (n − 1 ) ⋯ 1 {\displaystyle n!=n (n-1)\cdots 1}
, získáme log 2 (n ! ) ≥ log 2 ((n 2 ) n 2 ) = n 2 log n log 2 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).}
log 2 (n ! ) = Ω (n log n). {\displaystyle \ log _{2} (n!) = \Omega (n\log n).}
To poskytuje spodní část nároku. Lepší vázán může být dána prostřednictvím Stirlingova aproximace.
identická horní hranice vyplývá z existence algoritmů, které tuto hranici dosáhnou v nejhorším případě, jako jsou heapsort a mergesort.
výše uvedený argument poskytuje absolutní, nikoli pouze asymptotickou dolní hranici počtu srovnání, jmenovitě ⌈ log 2 (n ! ) {{\displaystyle \ left \ lceil \ log _ {2} (n!) \ right\rceil }
srovnání. Tato dolní mez je poměrně dobrá (lze k ní přistupovat v rámci lineární tolerance jednoduchým sloučením), ale je známo, že je nepřesná. Například ⌈ log 2 (13 ! )⌉ = 33 {\displaystyle \ left \ lceil \ log _ {2}(13!) \ right\rceil =33}
, ukázalo se však, že minimální počet srovnání s 13 prvky je 34.
určení přesného počtu srovnání potřebných k řazení daného počtu záznamů je výpočetně těžký problém i pro malé n A není znám žádný jednoduchý vzorec pro řešení. Pro některé z mála konkrétních hodnot, které byly vypočteny, viz OEIS: A036604.
dolní hranice pro průměrný počet srovnávačůeditovat
podobná hranice platí pro průměrný počet srovnání. Za předpokladu, že
- všechny klíče jsou odlišné, tj. každé srovnání bude dávat buď>b nebo a<b, a
- vstup je náhodná permutace, vybrané rovnoměrně z množiny všech možných permutací z n prvků,
je možné určit pořadí, ve kterém je vstup v s méně než log2(n!) srovnání v průměru.
to lze nejsnadněji vidět pomocí konceptů z teorie informace. Shannonova entropie takové náhodné permutace je log2 (n!) bit. Protože srovnání může poskytnout pouze dva výsledky, maximální množství informací, které poskytuje, je 1 bit. Proto po porovnání k je zbývající entropie permutace vzhledem k výsledkům těchto srovnání alespoň log2 (n!)- k bitů v průměru. Chcete-li provést třídění, jsou zapotřebí úplné informace, takže zbývající entropie musí být 0. Z toho vyplývá, že k musí být alespoň log2 (n!) v průměru.
dolní mez odvozená pomocí teorie informace je formulována jako “dolní mez informace-teoretická”. Informace-teoretická dolní mez je správná, ale nemusí být nutně nejsilnější dolní mez. A v některých případech může být informační teoretická dolní hranice problému dokonce daleko od skutečné dolní hranice. Pro příklad, informace-teoretická spodní hranice výběru je ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
vzhledem k tomu, n − 1 {\displaystyle n-1}
srovnání jsou potřebné sporné tvrzení. Souhra mezi informačně-teoretickou dolní mezí a skutečnou dolní mezí je podobně jako reálná funkce dolní ohraničující celočíselnou funkci. To však není přesně správné, pokud je zvažován průměrný případ.
Chcete-li zjistit, co se stane při analýze průměrného případu, klíčem je to, co znamená “průměr”? Průměr nad čím? S určitými znalostmi teorie informace, informačně-teoretické dolní mezní průměry nad množinou všech permutací jako celku. Ale všechny počítačové algoritmy (podle toho, co se v současné době věří) musí zacházet s každou permutací jako s individuální instancí problému. Průměrná dolní hranice, kterou hledáme, je tedy zprůměrována na všechny jednotlivé případy.
Chcete-li hledat dolní hranici týkající se nedosažitelnosti počítačů, přijmeme Model rozhodovacího stromu. Pojďme trochu přeformulovat, co je naším cílem. V modelu rozhodovacího stromu, dolní mez, která má být zobrazena, je dolní mez průměrné délky cest kořenů k listům n ! {\displaystyle n!}
– listový binární strom (ve kterém každý list odpovídá permutaci). Bylo by přesvědčeno, že vyvážený úplný binární strom dosahuje minima průměrné délky. S některými pečlivými výpočty, pro vyvážený plný binární strom s n ! {\displaystyle n!}
listy, průměrná délka cest kořenů k listům je dána (2 n ! – 2 log log 2 n n ! ⌋ + 1) log log 2 n n ! ⌉ + (2 log log 2 n n ! ⌋ + 1-n ! ) log log 2 n n ! 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!}}}
například Pro n = 3, informace-teoretická spodní hranice pro průměrný případ je přibližně 2.58, zatímco průměrná dolní mez získané prostřednictvím Rozhodovací strom model je 8/3, přibližně 2.67.
V případě, že se více položek může mít stejný klíč, neexistuje žádný zřejmý statistický výklad pojmu “průměrný případ”, tak argument jako výše nemohou být použity bez zvláštní předpoklady o rozložení kláves.
