Optimalita řazení založeného na porovnávání

Řadící algoritmy založené na porovnávání v každém svém kroku porovnají dvě hodnoty ze vstupního seznamu pomocí operace menší nebo rovno, čímž zjistí jejich uspořádání v rámci výsledného seřazeného seznamu.

Počet operací

Pokud má vstupní seznam prvků, pak existuje právě jeho různých uspořádání (permutací). Jelikož v každém kroku řadicí algoritmus porovná právě dva prvky, tak je zřejmé, že aby měl dostatek informací o daném seznamu, tak musí provést $2^{f(n)} \\geq n!$ kroků. Z této rovnosti pak vyplývá, že $f(n) \\geq \\log_{2}(n!)$ .

Asymptotická složitost

Horní odhad

Nejprve provedeme horní odhad, při kterém omezíme funkci $\\log_{2}(n!)$ funkcí $\\log_{2}(n^{n})$

$\\log_{2}(n^{n}) = n \\cdot \\log_{2}({n}) \\Rightarrow \\log_{2}(n!) \\in O(n \\cdot \\log_{2}({n}))$

Dolní odhad

Jako dolní odhad zvolíme funkci $\\log_{2}((n/2)^{n/2})$ , protože prvních n/2 členů funkce lze zdola omezit číslem n/2 , zbylé členy vychýlí funkci pouze vzhůru.

$n! = \\overbrace{n \\cdot (n-1) \\cdot (n-2) \\cdots (n/2)}^{n/2} \\cdots 1$

$\\log_{2}((n/2)^{n/2}) = n/2 \\cdot \\log_{2}(n/2) = {n \\over {2}} \\cdot (\\log_{2}(n) - \\log_{2}(2)) = {n \\over 2} \\cdot (\\log_{2}(n) - 1) = {n \\over 2} \\cdot \\log_{2}(n) - {n \\over 2}$ $\\Rightarrow \\log_{2}(n!) \\in \\Omega(n \\cdot \\log_{2}({n}))$

Výsledná složitost

Protože platí $\\log_{2}(n!) \\in O(n \\cdot \\log_{2}(n))$ a zároveň $\\log_{2}(n!) \\in \\Omega(n \\cdot \\log_{2}(n))$ , tak je složitost optimálního řadícího algoritmu založeného na porovnávání $\\Theta(n \\cdot \\log_{2}(n))$ .

Počet operací

Asymptotická složitost

Horní odhad

Dolní odhad

Výsledná složitost

Doporučujeme