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 n prvků, pak existuje právě n! 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 n! lze zdola omezit číslem n/2, zbylé členy vychýlí funkci n! 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)).








Doporučujeme