Editace stránky Dolní omezení pro porovnávací řazení

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

[[Soubor:Dolni-omezeni.jpg]]


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.


'''JE TO ŠPATNĚ !!!!!!!!!!!!!!! V TEXTU NEJSOU VIDĚT INDEX h^2 viz.: [http://www.kiv.zcu.cz/~netrvalo/vyuka/ppa2-11/ekniha/online/HTML/54/default.htm]'''


[[Kategorie:fav-kiv-bzinf]]