Algorytm magicznych piątek

Algorytm magicznych piątek (znany też jako „mediana median”) – 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.

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_{>}.$

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ę. 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\leqslant |A_{<}|$ to wywołujemy rekurencyjnie algorytm magicznych piątek dla pary $\langle A_{<},k\rangle .$ W przeciwnym wypadku jeśli $k\leqslant |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 .$

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 (rekurencyjnie) mediany zbioru $A_{5},$ wykonywanego w czasie $T\left({\frac {n}{5}}\right),$
• wykonania wywołania rekurencyjnego, wykonywanego co najwyżej w czasie $T(\max(|A_{<}|,|A_{>}|)).$

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

$T(n)\leqslant \Theta (n)+T\left({\frac {n}{5}}\right)+T\left({\frac {3n}{4}}\right).$

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.

Bibliografia

• Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ron L. Rivest i inni. Time bounds for selection. „Journal of Computer and System Sciences”. 7 (4), s. 448–461, 1973. DOI: 10.1016/S0022-0000(73)80033-9. [dostęp 2015-02-20]. (ang.). 
• Selekcja (materiały dydaktyczne MIMUW na studia informatyczne I stopnia). [dostęp 2015-02-23].