Lekce 7 - Dolní odhad složitosti problému třídění

V minulé lekci, Quick sort, jsme si ukázali algoritmus Quick sort i se zdrojovými kódy.

Každý, kdo se setkal s alespoň dvěma třídícími algoritmy, si jistě položil otázku, jestli může existovat algoritmus, který to udělá rychleji. A tím rychleji mám na mysli z hlediska (asymptotické) časové složitosti, tedy zda existuje kategoricky efektivnější algoritmus. Složitostí problému (nikoli složitostí algoritmu) je tedy myšlena složitost úlohy, tedy složitost nejlepšího možného algoritmu, který úlohu vyřeší. V některých případech algoritmus dokonce nemusí být ani známý, ale my budeme vědět, že existuje a že bude někdy objeven. Teď se zaměříme na problém třídění prvků.

Každý zde uvedený algoritmus nám dávál vlastně horní odhad složitosti problému třídění. Bubblesort měl časovou složitost O(n²), věděli jsme tedy, že třídit můžeme nejhůře s touto složitostí. Např. Heap sort však ten samý problém zvládl s časovou složitostí O(n log n). Automaticky víme, že to půjde nejhůře takto. Ale může existovat algoritmus s ještě lepší časovou složitostí? Budeme předpokládat, že ne a toto tvrzení se pokusíme dokázat. Dokazujeme tedy dolní složitost problému třídění, tedy že to nejde lépe než v O(n log n).

Důkaz

Pokud třídíme na základě porovnávání prvků (pro dvojice prvků určujeme, který je větší, resp. menší), můžeme každý takový algoritmus zapsat jako rozhodovací strom. Rozhodovací strom je binární strom, který ve vnitřních vrcholech obsahuje dvojice porovnávaných prvků a v listech jejich permutace. V každém listu je tedy uložen jeden možný výstup algoritmu, ve všech listech jsou potom všechny možnosti, jak mohou být prvky v poli seřazené.

Takový rozhodovací strom pro pole 2 prvků by byl jednoduchý, obsahoval by jen kořen, ve kterém bychom se zeptali: je a < b? Pokud ano, dostali bychom permutaci [a, b]. Pokud ne, dostali bychom [b, a] a bylo by setříděno. Rozhodovací strom však s přibývajícími prvky velmi rychle roste. Takhle by vypadal rozhodovací strom pro 3 prvky:

Pro 4 prvky by byl strom asi 4x větší.

Pokud třídíme n prvků, všech permutací těchto prvku bude celkem zcela jistě n!, strom tedy musí mít nejméně n! listů. Stromy hloupějších algoritmů jich budou mít mnohem více. Můžeme si představit, že ten úplně nejlepší algoritmus má ideální strom s n! listy. V nejhorším případě (když půjde po nejdelší větvi) při průchodu od kořene do listu udělá tolik porovnání, kolik má strom "úrovní", tedy jaká je výška stromu h.

Binární strom výšky h bude jistě obsahovat max. 2^h listů.

Jak jsem se zmínil výše, listů musí být nejméně n!, aby byl strom úplný, jinak by nějakou permutaci vstupních prvků nedokázal setřídit. Budeme tedy vycházet z nerovnice:

Po zlogaritmování dostaneme:

Nyní se podrobně zaměřme pouze na n! a na to, zda bychom ho nemohli pro naše potřeby nějak upravit. K dalším krokům by se nám velmi hodilo dostat místo n! výraz (n/2)^(n/2). Toho dosáhneme následujícím trikem:
Pro lepší představu jsem na ukázku přidal členy 8!. n! si můžeme rozepsat jako:

Jelikož v naší původní nerovnici bylo >= n!, můžeme si klidně dovolit n! zmenšit a nerovnost neporušíme. Vezmeme si tedy jen levou polovinu ze zápisu výše a tu pravou zahodíme.

Můžeme si dokonce dovolit nahradit všechny členy za n/2, protože každý člen je jistě >= n/2, nerovnost tedy opět neporušíme.

Výše uvedený výraz můžeme zapsat jako (n/2)^(n/2) a dosadit do původní nerovnice.

Upravujeme:

(mocnina šla před logaritmus, log. podílu je rozdíl logaritmů, log 2 je 1, tu zanedbám a zvýším jmenovatel). Dostáváme tedy h >= n/4 log n.

Což znamená, že každý algoritmus musí v nejlepším případě udělat porovnání (konstantu jsme schovali do symbolu Omega)

Dolní odhad složitosti problému třídění je a tedy nemůže existovat třídící algoritmus založený na vzájmeném porovnávání prvků s lepší časovou složitostí než touto. Všimněte si, že jsem zdůraznil založený na vzájmeném porovnávání prvků. Že by to přeci jen šlo rychleji? O tom je následující článek - Counting sort

V další lekci, Counting sort, si ukážeme algoritmus Counting sort i se zdrojovými kódy.