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))$ .

{ zpětná vazba }

Tweet		Delicious
Sdílet

Hodnocení (1): 5

Přečtěte si také

Porovnání algoritmů

Diskuse

Pavel Mička7.11.2010

Máš pravdu, nějak jsem u té úpravy smíchal dva postupy dohromady (a nedávalo to smysl). Typografie taky opravena. V závěru jsem vyměnil prvni Omegu za Omicron, protože to je první v článku uvedená rovnost.
Díky.

Palec7.11.2010

A samozřejmě jsem v tom udělal chybu také... Tak ještě jednou.
(n/2) * log2(n/2) = (n/2) * (log2(n) - log2(2)) = (n/2) * (log2(n) - 1) = (n/2) * log2(n) - n/2

Palec7.11.2010

Úprava logaritmu pro spodní odhad mi nepřijde v pořádku. S první úpravou souhlasím (logaritmus mocniny), ale v druhém kroku není správně použito pravidlo pro logaritmus podílu. Po úpravě má vyjít (n/2) * (log2(n) - log2(n)) = (n/2) * (log2(n) - 1) = (n/2) * log2(n) - n/2. Z čistě typografického hlediska bych ještě upozornil na zápis logaritmu, který je po druhé úpravě najednou kurzivou.
Závěr obsahuje překlep - místo druhé omegy by mělo být O.