Každá slušná učebnice algoritmů vysvětlí, jak rychlé jsou třídicí algoritmy jako quicksort a heapsort, ale není třeba bláznivé matematiky, abyste dokázali, že jsou asymptoticky rychlé, jak jen to jde.
Pedantická poznámka k zápisu
Většina informatiků používá zápis big-O ve významu „asymptoticky stejný až po konstantní škálovací faktor“, což pro ostatní matematiky neznamená úplně to samé. Omlouvám se, budu používat big-O jako v učebnicích CS, ale alespoň ho nebudu směšovat s jinými matematickými zápisy.
Podívejme se na speciální případ algoritmů, které porovnávají hodnoty po dvou (jako quicksort a heapsort a většina dalších populárních algoritmů). Myšlenky lze později rozšířit na všechny třídicí algoritmy.
Jednoduchý argument pro počítání v nejhorším případě
Předpokládejme, že máme pole čtyř prvků, všechny různé, v náhodném pořadí. Lze jej seřadit porovnáním pouze jednépáry prvků? Zřejmě ne, ale zde je jeden dobrý důvod, který dokazuje, že nemůžete: Podle definice, abyste mohli pole seřadit,musíte jak prvky přeskládat, aby se seřadily. Jinými slovy, musíte vědět, jakou permutaci potřebujete. Kolik možných permutací existuje? První prvek může být přesunut na jedno ze čtyř míst, druhý může jít na jedno ze zbývajících tří, třetí prvek má dvě možnosti a poslední prvek musí zaujmout zbývající místo. Existuje tedy 4×3×2×1=4!=244 \krát 3 \krát 2 \krát 1 = 4! = 24 možných permutací na výběr, ale existují pouze dva možné výsledky porovnání dvou různých věcí: „VĚTŠÍ“ a „MENŠÍ“. Kdybyste si sestavili seznam všech možných permutací, mohli byste se rozhodnout, že „VĚTŠÍ“ znamená, že potřebujete permutaci č. 8, a „MENŠÍ“ znamená, že potřebujete permutaci č. 24, ale nemůžete vědět, kdy potřebujete ostatních 22 permutací.
Při dvou porovnáních máte 2×2=42 \krát 2 = 4 možné výsledky, což stále nestačí. Nemůžete roztřídit všechna možná zamíchaná pole, pokud neprovedete alespoň pět porovnání (25=322^5 = 32). Jestliže W(N)W(N) je nejhorší možný počet porovnání potřebných ke třídění různých prvků NN pomocí nějakého algoritmu, můžeme říci
2W(N)≥N!2^{W(N)}. \geq N!
Při logaritmování o základu 2,
W(N)≥log2N!W(N) \geq \log_2{N!}
Asymptoticky N!N! roste jako NNN^N (viz také Stirlingova formule), takže
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
A to je O(NlogN)O(N\log N) limit na nejhorší případ jen z počítání výstupů.
Prostřední případ z teorie informací
Můžeme získat silnější výsledek, pokud tento argument o počítání rozšíříme o trochu teorie informací. Zde je návod, jak bychom mohli použít třídicí algoritmus jako kód pro předávání informací:
- Přemýšlím o čísle – řekněme 15
- Vyhledám permutaci č. 15 ze seznamu permutací čtyř prvků
- Pustím na této permutaci třídicí algoritmus a zaznamenám všechny výsledky porovnání „VĚTŠÍ“ a „MENŠÍ“
- Předám vám výsledky porovnání v binárním kódu
- Vy si znovu zopakujete běh mého třídicího algoritmu, krok za krokem, přičemž se podle potřeby odvoláváte na můj seznam výsledků porovnání
- Teď, když víte, jak jsem své pole přeuspořádal, aby bylo setříděné, můžete permutace obrátit a zjistit mépůvodní pole
- Podíváte se na mé původní pole v seznamu permutací a zjistíte, že jsem přenesl číslo 15
Dobře, je to trochu divné, ale šlo by to. To znamená, že třídicí algoritmy jsou vázány stejnými zákony jakonormální kódovací schémata, včetně věty dokazující, že neexistuje univerzální datový kompresor. Na každé porovnání, které algoritmus provede, jsem přenesl jeden bit, takže podle teorie informace musí být počet porovnání v průměru alespoň takový, kolik bitů je potřeba k reprezentaci mých dat. Techničtěji řečeno, průměrný počet porovnání musí být alespoň Shannonova entropie mých vstupních dat, měřeno v bitech. Entropie je matematická míra informačního obsahu nebo nepředvídatelnosti něčeho.
Mám-li pole prvků NN, které mohou být v jakémkoli možném pořadí bez zkreslení, pak je entropie maximální a činílog2N!\log_2{N!} bitů. To dokazuje, že O(NlogN)O(N\log{N}) je optimální průměr pro třídění založené na porovnávání s libovolným vstupem.
Taková je teorie, ale jak jsou na tom skutečné třídicí algoritmy? Níže je graf průměrného počtu porovnánípotřebných k setřídění pole. Teoretické optimum jsem porovnal s naivním quicksortem a Ford-Johnsonovým tříděním sloučením a vložením, které bylo navrženo tak, aby minimalizovalo porovnávání (i když je celkově zřídka rychlejší než quicksort, protože v životě jde o víc než o minimalizaci porovnávání). Od roku 1959, kdy bylo merge-insertion sort vyvinuto, bylo vylepšeno, aby se z něj vytlačilo několik dalších porovnání, ale graf ukazuje, že je již téměř optimální.
Je hezké, když trocha teorie dává tak těsný praktický výsledek.
Dosavadní shrnutí
Tady je to, co se zatím podařilo dokázat:
- Pokud by pole mohlo začínat v libovolném pořadí, je v nejhorším případě potřeba alespoň O(NlogN)O(N\log{N}) porovnání
- Průměrný počet porovnání musí být roven alespoň entropii pole, což je O(NlogN)O(N\log{N}) pro náhodný vstup
Všimněte si, že #2 umožňuje, aby algoritmy třídění založené na porovnávání byly rychlejší než O(NlogN)O(N\log{N}), pokud je vstup málo entropický (jinými slovy předvídatelnější). Slučovací třídění se blíží O(N)O(N), pokud vstup obsahuje mnoho tříděných dílčích polí. Insertion sort se blíží O(N)O(N), pokud je vstupem pole, které bylo setříděno před tím, než bylo trochu narušeno. Žádný z nich v nejhorším případě nepřekonáO(NlogN)O(N\log{N}), pokud nejsou některá uspořádání polí jako vstupy nemožná.
Obecné třídicí algoritmy
Třídění založené na porovnávání je v praxi zajímavý zvláštní případ, ale teoreticky na něm není nic zvláštníhoCMP na rozdíl od jakékoli jiné instrukce na počítači. Oba výše uvedené argumenty lze zobecnit na jakýkoli třídicí algoritmus, pokud si všimnete několika věcí:
- Většina počítačových instrukcí má více než dva možné výstupy, ale stále jich má omezený počet
- Omezený počet výstupů znamená, že jedna instrukce může zpracovat jen omezené množství entropie
To nám dává stejnou O(NlogN)O(N\log{N}) dolní mez počtu instrukcí. Jakýkoli fyzicky realizovatelný počítač může zpracovávat pouze omezený počet instrukcí najednou, takže to je také O(NlogN)O(N\log{N}) dolní mez na potřebný čas.
Ale co „rychlejší“ algoritmy?
Nejužitečnější praktický důsledek obecné meze O(NlogN)O(N\log{N}) je, že pokud slyšíte o nějakém asymptoticky rychlejším algoritmu, víte, že musí nějak „podvádět“. Musí v tom být nějaký háček, který znamená, že se nejedná o třídicí algoritmus pro obecné použití, který se škáluje na libovolně velká pole. Možná je to stále užitečný algoritmus, ale je dobré si pozorně přečíst drobné písmo.
Známým příkladem je radix sort. Často se mu říká třídicí algoritmus O(N)O(N), ale háček je v tom, že funguje pouze tehdy, pokud se všechna čísla vejdou do kk bitů, a ve skutečnosti je to O(kN)O(kN).
Co to znamená v praxi? Předpokládejme, že máte 8bitový stroj. V 8 bitech můžete reprezentovat 28=2562^8 = 256 různých čísel, takže pokud máte pole tisíců čísel, budete mít duplicity. To může být pro některé aplikace v pořádku, ale pro jiné je třeba přejít alespoň na 16 bitů, které mohou zřetelně reprezentovat 216=65 5362^16 = 65 536 čísel. 32 bitů bude podporovat 232=4 294 967 2962^32 = 4 294 967 296 různých čísel. S rostoucí velikostí pole bude mít tendenci růst i počet potřebných bitů. Pro zřetelnou reprezentaci NN různých čísel budete potřebovat k≥log2Nk \geq \log_2{N}. Pokud vám tedy nevadí spousta duplicit v poli, je O(kN)O(kN) ve skutečnosti O(NlogN)O(N\log{N}).
Potřeba O(NlogN)O(N\log{N}) vstupních dat v obecném případě vlastně sama o sobě dokazuje celkový výsledek. Tento argument není v praxi tak zajímavý, protože málokdy potřebujeme třídit miliardy celých čísel na 32bitovém stroji, a pokud někdo narazil na limity 64bitového stroje, neřekl to nám ostatním.