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

Verze z 20. 2. 2014, 06:36

Celkem HC otázka, asi nejtěžší z PPA, kvůli matematice, kterou my programátoři moc nemusíme (kdo říká, že to není pravda, tak lže sám sobě, nebo neumí programovat s tím, co je k dispozici a vše si musí do podrobna analyzovat)

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 = 2h (binární strom má maximálně 2h 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!) = log2 2h = h log22 = h * 1 = h = počet porovnání, kterým se dostneme k permutaci

Použitim aproximace (n/e)n = n! je

log2(n!)=n * log2 (n/e) = log2 n- n* log2 e,

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

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