Algorytm magicznych piątek

Z Wikipedii

Algorytm magicznych piątek to algorytm rozwiązujący problem selekcji, czyli znalezienia $k$ -tej co do wielkości spośród $n$ liczb. Zaproponowali go Blum, Floyd, Pratt, Rivest i Tarjan w roku 1973. Jest on oparty na prostszym algorytmie rozwiązującym ten sam problem, algorytmie Hoare'a.

[edytuj] Idea algorytmu

Załóżmy, że dany jest zbiór $n$ liczb $A$ , szukamy w nim $k$ -tej liczby co do wielkości. Pomysł polega na ulepszeniu algorytmu Hoare'a, mianowicie na dokonaniu podziału względem sensownego elementu i to tym razem na trzy zbiory, mniejszych, równych oraz większych od wybranej liczby. Przypomnijmy, że algorytm Hoare'a polega na wybraniu losowego elementu, dokonaniu podziału zbioru $A$ na elementy mniejsze lub równe od niego oraz na elementy większe od niego, a następnie rekurencyjne wywołanie algorytmu dla odpowiedniego z tych dwóch zbiorów. Idea algorytmu magicznych piątek polega na tym, żeby znaleźć w zbiorze $A$ taki element, który zapewni podział na stosunkowo równe zbiory elementów mniejszych $A <$ i większych $A >$ .

[edytuj] Algorytm

Algorytm jest rekurencyjny. Dzielimy zbiór $A$ na piątki liczb (ewentualnie ostatnia piątka jest niepełna) i spośród każdej piątki wybieramy medianę, czyli w każdej pełnej piątce liczbę trzecią co do wielkości. Oznaczmy zbiór tych median przez $A 5$ . Następnie wywołujemy rekurencyjnie algorytm magicznych piątek dla pary $\langle A_5,\lfloor\frac{|A_5|}{2}\rfloor\rangle$ , czyli innymi słowy szukamy w zbiorze $A 5$ mediany, niech wynikiem będzie liczba $m 5$ .

Liczba $m 5$ jest dobrym elementem do wykonania podziału. Zauważmy, że w zbiorze $A$ , w każdej z piątek, której reprezentant okazał się mniejszy lub równy od $m 5$ przynajmniej połowa (a w większości przypadków trzy piąte) elementów jest nie większa od $m 5$ . Zatem przynajmniej jedna czwarta liczb ze zbioru $A$ jest nie większa od $m 5$ , analogicznie można uzasadnić, że przynajmniej jedna czwarta jest nie mniejsza.

Dokonujemy zatem podziału zbioru $A$ na liczby mniejsze od $m 5$ (zbiór $A <$ ), równe $m 5$ (zbiór $A =$ ) oraz większe od niej (zbiór $A >$ ). Jeśli $k\leq|A_<|$ to wywołujemy rekurencyjnie algorytm magicznych piątek dla pary $\langle A_<,k\rangle$ . W przeciwnym wypadku jeśli $k\leq|A_<|+|A_=|$ to zwracamy $m 5$ jako $k$ -tą liczbę, a jeśli nie, to wywołujemy rekurencyjnie algorytm dla pary $\langle A_>,k-|A_<|-|A_=|\rangle$ .

[edytuj] Analiza złożoności

Niech $T (n)$ oznacza złożoność czasową algorytmu. Zauważmy, że wykonanie algorytmu składa się z trzech kroków

znajdowania median piątek, wykonywanego w czasie $\Theta(n)\!$
wybierania mediany zbioru $A 5$ , wykonywanego w czasie $T(\frac{n}{5})$
wykonania wywołania rekurencyjnego, wykonywanego co najwyżej w czasie $T(\max(|A_<|,|A_>|))\!$

Jak wcześniej zauważyliśmy $T(\max(|A_<|,|A_>|))\leq\frac{3n}{4}$ , zatem szacując czas wykonania całego algorytmu przez sumę maksymalnych czasów wykonań kroków dostajemy nierówność

$T(n)\leq\Theta(n)+T(\frac{n}{5})+T(\frac{3n}{4})$ .

Stosując standardowe metody rozwiązywania nierówności asymptotycznych (kluczowe jest, że $\frac{1}{5}+\frac{3}{4}=\frac{19}{20}<1$ ) dostajemy, że algorytm magicznych piątek nawet pesymistycznie jest liniowy.