Na záver si ešte poďme niečo povedať o tom, ako rýchlo vlastne vieme triediť.
Čo robia triedenia porovnávaním? Porovnávajú prvky medzi sebou a podľa toho ich vymieňajú. Môžete si
všimnúť, že merge sort aj quick sort mali $O(n\log n)$ porovnaní. Otázkou však je,
či je toto najlepšie možné riešenie, či sa to nedá zlepšiť. Hľadáme teda dolnú hranicu na počet
porovnaní, ktoré potrebuje ľubovoľný algoritmus.
Predstavme si, že algoritmy trochu upravíme. Najskôr spravia všetky porovnania a až potom prvky povymieňajú. Môžete si rozmyslieť, že takto sa na nich nič nezmení. Taktiež množina výmen je jednoznačne určená porovnaniami, ktoré algoritmus urobí. Taktiež sa zamýšľajme len nad postupnosťami, kde prvky tvoria permutáciu čísel $1$ až $n$. Uvedomte si, že pre algoritmus je to absolútne nerozlíšiteľné a nám to pomôže v argumentácii.
Počet výmen, ktoré algoritmus reálne potrebuje na to, aby pole utriedil, je relatívne malý, vždy mu stačí $O(n)$ výmen. Problém však je, že vtedy si už algoritmus musí byť istý, ktorú permutáciu má pred sebou. Nemôžu mu zostať dve, lebo by sa mohol pomýliť. Nakreslime si teda takzvaný rozhodovací strom. Vrchol tohto stromu bude tvoriť porovnanie, ktoré algoritmus urobí. Z každého vrchola pôjdu dve hrany, podľa odpovede, ktorú dostane a listy stromu budú možné permutácie, ktoré mohol dostať. Keďže permutácií $n$ prvkov je $n!$, tak aj takýto strom má teda $n!$ listov.
Každému algoritmu zodpovedá jeden takýto rozhodovací strom. Našou úlohou bude dokázať, že vždy obsahuje cestu dĺžky aspoň $O(n\log n)$. Tým pádom existuje vstup, na ktorom bude musieť spraviť aspoň toľko porovnaní a dokážeme, že potrebujeme zložitosť $\Omega (n\log n)$.
Poďme sa pozrieť na to, koľko úrovní (akú hĺbku) musí mať náš rozhodovací strom. Na prvej úrovni je jeden vrchol. Na druhej úrovni sú najviac dva, na tretej najviac štyri atď. To znamená, že $n!$ vrcholov a teda aj listov sa môže prvýkrát objaviť v hĺbke $\log n!$. Tým pádom dolná hranica na počet porovnaní je $\log n!$. Poďme si toto číslo odhadnúť.
Zhora vieme spraviť jednoduchý odhad $n^n \geq n!$. Zdola môžeme spraviť nasledovný odhad. Prvých $n/2$ členov faktoriálu, je väčších ako $n/2$, teda $n! \geq (n/2)^{n/2}$. Dostaneme teda $n^n \geq n! \geq (n/2)^{n/2}$. Po zlogaritmovaní: $n\log n \geq \log n! \geq \frac{n}{2} \log \frac{n}{2}$. A v $O$ notácii dostanem $O(n\log n) \geq O(\log n!) \geq O(n\log n)$, teda $O(\log n!) = O(n \log n)$.
Smutný a zároveň veselý výsledok. Smutný je, lebo je nám jasné, že nevieme triediť rýchlejšie, čo je však oveľa lepšie, máme optimálne riešenie tohoto problému. A to je obrovský úspech, na ktorý môžeme ako informatici byť právom hrdí.
Zrejme vás ale napadne, že tu niečo nesedí, veď predsa sami ste naprogramovali triedenie, ktorého časová zložitosť bola $O(n)$ - countsort. Chyták je v jednom (podstatnom) detaile. Celý tento text sme sa rozprávali o triedeniach, ktoré fungujú na základe porovnávania. Jediný spôsob, ako vedia získavať informácie o prvkoch je, že dva prvky porovnajú. V prípade countsortu sme ale využívali niečo trochu iné. My sme vedeli, že triedené prvky sú celé čísla a dokonca, že sú z nejakého rozsahu, a túto vedomosť sme využili na utriedenie poľa v časovej zložitosti $O(n)$. Napríklad, situácia, kde by count sort nešiel takto jednoducho použiť, je napríklad, ak by ste chceli triediť desatinné čísla.