10.4 QuickSelect

1 Úvod 2 Grafy 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 10.1 Řazení 10.2 Základní řadící algoritmy 10.3 Merge Sort 10.4 QuickSelect 11 Dynamické programování Index Literatura

Příklad 10.1 (Hledání $k$-tého nejmenšího prvku v neseřazené posloupnosti)

Na vstupu je neseřazená posloupnost $X$ o velikosti $n$ prvků a číslo $k$, $k \le n$. Cílem je najít $k$-tý nejmenší prvek v $X$.

Zobrazit řešení

Problém triviálně vyřešit seřazením posloupnosti v čase $O(n \log n)$.

Elegance následujícího řešení spočívá v tom, že problém řeší řádově rychleji bez nutnosti vstupní posloupnost seřadit

Pozorování 10.4 (Idea rychlého algoritmu výběru QuickSelect)

Vybereme ze vstupní posloupnosti X nějaký prvek, tzv. pivot.

Vstupní posloupnost poté rozdělíme na tři části:

Na levou část $L$, do které přesuneme prvky menší než pivot
Na prostřední část $S$, do které přesuneme prvky rovné pivotovi
Na pravou část $P$, do které přesuneme prvky větší než pivot

Kdybychom posloupnost hypoteticky seřadili, bude tvořena nejdříve seřazenou částí L, pak všemi prvky z S a konečně seřazenou částí P.

\begin{algorithm}
\begin{algorithmic}
\IF { $n = 1$ }
    \RETURN $x_1$
\ENDIF
\STATE $p$ := některý z prvků $x_1, . . . , x_n$ //pivot
\STATE $L$ := prvky z $x_1, . . . , x_n$, které jsou menší než $p$
\STATE $S$ := prvky z $x_1, . . . , x_n$, které jsou rovny $p$
\STATE $P$ := prvky z $x_1, . . . , x_n$, které jsou větší než $p$
\IF { $k \le |L|$ }
    \RETURN QuickSelect($L$, $k$)
\ELIF { $k \le |L| + |S|$ }
    \RETURN $p$
\ELSE
    \RETURN QuickSelect($P$, $k − |L| − |S|$)
\ENDIF\end{algorithmic}
\end{algorithm}

Algoritmus 10.4: QuickSelect ($x_1, ..., x_n$; $k$)

Pozorování 10.5 (Volba pivota pro nejhorší časovou složitost)

Rozdělení vstupní posloupnosti na $L$, $S$, $P$ trvá lineární čas.

Pak se QuickSelect rekurzivně zavolá na část $L$ nebo $P$.

O kolik bude tato část menší než $n$, to závisí zejména na hodnotách ve vstupní posloupnosti a na způsobu výběru pivota.

Příklad scénáře vedoucího na nejhorší časovou složitosti:

Zvolíme-li pivota jako největší prvek vstupu, bude $|L| = n − 1$.
Pokud navíc bude $k = 1$, bude se QuickSelect rekurzivně volat právě na $L$.
To se v nejhorším případě může opakovat, takže celková časová složitost v nejhorším případě bude $Θ(n) + Θ(n − 1) + · · · + Θ(1) = Θ(n^2)$.

Pozorování 10.6 (Volba pivota pro lepší časovou složitost)

Příklad scénáře vedoucího na nejlepší časovou složitosti:

Ideální volbou pivota by byl medián dané (pod)posloupnosti.
$|L|$ i $|P|$ by byla nejvýše $⌊n/2⌋$ (neboť $|S| ≥ 1$) a délky podposloupností by v rekurzi exponenciálně rychle klesaly.
Pokud bychom medián dokázali najít v lineárním čase, bude čas $\Theta(n) + \Theta(n/2) + \Theta(n/4) + · · · + \Theta(1) = \Theta(n)$.

K tomuto ideálnímu řešení se můžeme přiblížit tak, že místo mediánu použijeme tzv. skoromedián.

Skoromedián je prvek, který leží kdekoli v prostředních dvou čtvrtinách seřazené posloupnosti.
Skoromedián bude tedy mít nalevo i napravo vždy nejvýše $3/4 \cdot n$ prvků.
Velikost vstupu bude tedy i v nejhorším případě opět exponenciálně klesat, byť pomaleji:
\begin{equation*} O(n) + O(3/4 · n) + O((3/4)2 · n) + · · · + O(1), \end{equation*}

což je opět geometrická řada se součtem $O(n)$.

Poznámka 10.2 (Jak hledat skoromedián?)

Pro libovolnou vstupní posloupnost platí z definice, že nejméně polovina jejích prvků jsou skoromediány, viz malý příklad níže.

Pokud budeme pivota vybírat náhodně, je pravděpodobnost výběru skoromediánu nejméně 1/2.

Pro ověření, že náhodně vybraný prvek je skoromedián, je třeba celou posloupnost projít, tedy lineární čas.

Dostáváme tak hezkou ukázku užitečné a efektivní randomizace algoritmu.

Pozorování 10.7 (Popis QuickSelectu s náhodným výběrem pivota)

Nalezneme skoromedián neseřazené posloupnosti $n$ prvků:

Vybereme rovnoměrně náhodně jeden z prvků posloupnosti ($O(1)$ čas).
Ověříme, je-li vybraný prvek skoromedián ($\Theta(n)$ čas).
Pokud ne, celý postup opakujeme.

Protože pravděpodobnost, že se náhodným výběrem strefíme do skoromediánu, je nejméně 1/2, potřebujeme k nalezení skoromediánu ve střední hodnotě 2 pokusy.

To vyplývá z Věty o opakování nezávislých pokusů

Počet pokusů v nejhorším případě samozřejmě neumíme nijak omezit, ale pravděpodobnost, že se do skoromediánu nebudeme opakovaně strefovat, bude s počtem pokusů klesat k nule.

\begin{algorithm}
\begin{algorithmic}
\IF { $n = 1$ }
    \RETURN $x_1$
\ENDIF
\STATE $p$ := $x_{random(1, n)}$ //pivot
\IF { $p$ není skoromedián v $x_1, ..., x_n$ }
    \STATE Jdi na řádek $4$
\ENDIF
\STATE $L$ := prvky z $x_1, . . . , x_n$, které jsou menší než $p$
\STATE $S$ := prvky z $x_1, . . . , x_n$, které jsou rovny $p$
\STATE $P$ := prvky z $x_1, . . . , x_n$, které jsou větší než $p$
\IF { $k \le |L|$ }
    \RETURN RandomQuickSelect($L$, $k$)
\ELIF { $k \le |L| + |S|$ }
    \RETURN $p$
\ELSE
    \RETURN RandomQuickSelect($P$, $k − |L| − |S|$)
\ENDIF\end{algorithmic}
\end{algorithm}

Algoritmus 10.5: RandomQuickSelect($x_1, ..., x_n$; $k$)

Věta 10.5 (Časová složitost `RandomQuickSelect`)

Střední hodnota počtu výpočetních operací vykonaných algoritmem RandomQuickSelect ($x_1, ... , x_n$; $k$) s náhodným výběrem pivota je $\mathcal{O}(n)$.

Zobrazit důkaz

Rozdělíme běh algoritmu RandomQuickSelect na fáze podle hloubky rekurze.

V každé fázi zvolíme náhodně pivota, což zahrnuje ověření v lineárním čase, že se jedná o skoromedián. Pak provedeme v lineárním čase rozdělení na $L$, $S$, $P$ a pokud neskončíme, přejdeme do další rekurzivní fáze s $L$ nebo $P$ na vstupu.

Během každé fáze se vstup zmenší nejméně o čtvrtinu.

V $i$-té fázi je tedy na vstupu nejvýše $\left( \frac{3}{4} \right)^{i−1} \cdot n$ prvků.

Definujme náhodnou veličinu $T_i =$ počet výpočetních operací (přesunů, porovnání, atp) $i$-té fáze.

Pak platí

\begin{equation*} E[T_i] \le \left( \frac{3}{4} \right)^{i−1} \Theta(n) \cdot E[\text{# pokusů k nalezení skoromediánu}] \le \left( \frac{3}{4} \right)^{i−1} \Theta(n) \cdot 2. \end{equation*}

Náhodná veličina celkového počtu operací algoritmu $T$ je tedy $T = T_1 + T_2 + · · · + T_l$, kde $l = \Theta(\log n)$.Využitím linearity střední hodnoty

\begin{align*} E[T] &= E[T_1 + … + T_l] \\ &\le \sum_{i=1}^l \left( \frac{3}{4} \right)^{i−1} \cdot \Theta(n) = \Theta(n)\end{align*}

Tedy i v nejhorším případě skoromediánu na hranicích vnitřních dvou čtvrtin vstupní posloupnosti je střední hodnota počtu výpočetních operací $O(n)$, což je optimální složitost

$\square$

Pozorování 10.8 (Dva přístupy k randomizaci QuickSelectu)

Algoritmus RandomQuickSelect poskytuje ve střední hodnotě optimální časovou složitost pro libovolné vstupní posloupnosti tím, že pivot se vybírá náhodně a při tom o vstupní posloupnosti nic nepředpokládáme.

Uvažme obrácený přístup: Předpokládejme, že jako pivota vždy volíme deterministicky prvek na fixní (např. první) pozici, ale že vstupní pole jsou dokonale náhodné posloupnosti, čili každá permutace bude vstupem s pravděpodobností $1/n!$.

Průměrná časová složitost QuickSelectu bude průměrem časových složitostí běhu algoritmu přes všech $n!$ vstupů. Pro praktickou implementaci bychom potřebovali umět dokonale náhodně permutovat vstupní posloupnosti. To zde popsáno nebude.

Naznačíme si teď důkaz, že takto definovaná složitost je opět $O(n)$

Věta 10.6 (Deterministický `QuickSelect` s náhodnými vstupy)

Uvažujme na vstupu rovnoměrně náhodnou permutaci $\{1, ... , n\}$.

Jako pivota volíme prvek na první pozici. Potom střední hodnota počtu operací vykonaných při jednom běhu algoritmu je $O(n)$.

Vzhledem k náhodnosti vstupu je první prvek rovnoměrně náhodně vybrané číslo z množiny $\{1, 2, ..., n\}$.

S pravděpodobností $\frac{1}{2}$ se tedy trefíme do skoromediánu vstupu. Po rozdělení vstupu na levou a pravou část budou obě části opět náhodné permutace, na nichž se algoritmus chová stejně.

Lze tedy použít stejnou analýzu jako u RandomQuickSelectu s tím rozdílem, že hloubka zanoření rekurze bude ve střední hodnotě dvojnásobná a v průměru každé dvě hladiny sníží velikost problému na aspoň $\frac{3}{4}$ předchozí.