Algorytm magicznych piątek

Algorytm magicznych piątek, algorytm Bluma-Floyda-Pratta-Rivesta-Tarjana (ang. median of medians) – algorytm rozwiązujący problem selekcji, czyli znalezienia ${\displaystyle k}$-tej co do wielkości spośród ${\displaystyle 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 ${\displaystyle n}$ liczb ${\displaystyle A,}$ szukamy w nim ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle A}$ taki element, który zapewni podział na stosunkowo równe zbiory elementów mniejszych ${\displaystyle A_{<}}$ i większych ${\displaystyle A_{>}.}$

Algorytm

Algorytm jest rekurencyjny. Dzielimy zbiór ${\displaystyle 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 ${\displaystyle A_{5}.}$ Następnie wywołujemy rekurencyjnie algorytm magicznych piątek dla pary ${\displaystyle \langle A_{5},\lfloor {\frac {|A_{5}|}{2}}\rfloor \rangle ,}$ czyli innymi słowy szukamy w zbiorze ${\displaystyle A_{5}}$ mediany, niech wynikiem będzie liczba ${\displaystyle m_{5}.}$

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

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

Analiza złożoności

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

Jak wcześniej zauważyliśmy ${\displaystyle \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ść

${\displaystyle 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 ${\displaystyle {\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].