Vypočitatelnost a výpočtová složitost
Dolní omezení pro porovnávací řazení
 Vytisknout studijní materiál

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

Vraťme se k problému řazení a jeho řešení algoritmy využívajícími jenom porovnávání řazených prvků. Zkoumejme dolní omezení počtu porovnání T(n) pro porovnávací algoritmy řazení, to znamená, že počet porovnání pro seřazení n prvků musí být větší než nějaká hodnota g(n).

Předpokládejme, že všechny prvky posloupnosti

a1, a2, ..., an

jsou různé. Porovnávací řazení můžeme znázornit rozhodovacím stromem. Ve vnitřních vrcholech jsou prvky, které algoritmus porovná a v listech je permutace všech prvků původní posloupnosti, která je seřazena.

Příklad rozhodovacího stromu pro řazení vkládáním tří prvků a1,a2,a3 je na obr.. V prvním kroku porovnáme prvky s indexy 1 a 2. Ve druhém kroku jsou-li ve správném pořadí porovnáme prvky s indexy 2 a 3. Nebyly-li ve správné pořadí jsou algoritmem vyměněny v prvním kroku a ve druhém kroku, v tomto případě porovnáváme prvky s indexy 1 a 3. Celý postup pokračuje až v listu stromu jsou indexy v pořadí, které vyjadřuje permutaci, ve které jsou prvky a1,a2,a3 seřazeny.

Jakýkoliv správný algoritmus musí v rozhodovacím stromu vytvořit každou z n! permutací prvků původní posloupnosti, aby dokázal seřadit jakoukoliv vstupní posloupnost. Každá z těchto permutací musí být alespoň v jednom listě.

Podíváme-li se na obr. vidíme, že nejhorším případem počtu porovnání vykonaných algoritmem řazení je nejdelší cesta od kořene stromu k listu, je tedy

T(n) = h

Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovací strom o výšce h l listů, potom l ≤ 2h. Současně listů musí být alespoň tolik kolik je permutací, tedy n! ≤ l. Potom

n! ≤ l ≤ 2h

a logaritmováním

log2 (n!) ≤   h = T(n)

Použitím aproximace (n/e)n pro n! je log2(n!)=n*log2 n- n* log2 e,

čím dostáváme dolní omezení pro nejhorší případ Ω(n*log2 n).

Protože pro řazení haldou a slučováním je horní omezení času výpočtu O(n*log2 n) jsou tato řazení asymptoticky optimální.