Dolní omezení pro porovnávací řazení

Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.

Předpokladejme, že všechny prvky posloupnosti a1, a2, ..., an jsou různé. Porovnavací řazeni můžeme znázornit rozhodovacim stromem. Ve vnitřních vrcholech jsou prvky, ktere algoritmus porovná a v listech je permutace všech prvků původni posloupnosti, ktera je seřazena.

Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků: Jakykoliv 100% správný algoritmus (brutální síla) musi vytvořit každou z n! permutací prvků původní posloupnosti a zjistit, která je seřazená. Každou z takových permutací umístíme do stromu, ve kterém je v kořenech naznačeno porovnání, kterým se k permutacím dostaneme.

Nejhoršim připadem počtu porovnani vykonanych algoritmem řazeni je nejdelši cesta od kořene stromu k listu, je tedy rovna vyšce stromu T(n) = h .

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2^h (binární strom má maximálně 2^h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! <= l. Potom n! <= l <= 2h a po logaritmování (zjištění délky cesty, každá vrstva x grafu má 2x možných cest (2x listů), takže číslo vrstvy a tedy i délka ke kořeni je funkce inverzní, tedy log2x)

log2 (n!) <= log_2(2^h) | h*log_2(2) -> h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim levé části aproximace e*(n/e)^2 <= n! <= e*((n+1)/e)^(n+1) se dostáváme na:

log_2(n!) ~ n * log_2 (e*(n/e)) = n*(log_2(e) + log_2(n) - log_2(e))

čim dostavame dolni omezeni pro nejhorši připad Ω(n*log_2(n)).

Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.