Algorytm magicznych piątek
Algorytm magicznych piątek, znany również jako algorytm Bluma-Floyda-Pratta-Rivesta-Tarjana (ang. median of medians), to metoda służąca do rozwiązania problemu selekcji, a konkretnie do znajdowania k-tej co do wielkości liczby spośród n liczb. Algorytm ten został opracowany przez Bluma, Floyda, Pratta, Rivesta i Tarjana w 1973 roku i opiera się na prostszej metodzie, znanej jako algorytm Hoare’a.
Idea algorytmu
Załóżmy, że mamy zbiór A składający się z n liczb, w którym poszukujemy k-tej liczby co do wielkości. Kluczowym założeniem jest poprawienie algorytmu Hoare’a poprzez dokonanie podziału na trzy zbiory: mniejsze, równe oraz większe od wybranego elementu. Przypomnijmy, że algorytm Hoare’a polega na losowym wyborze elementu, który dzieli zbiór A na elementy mniejsze lub równe oraz większe, a następnie na rekurencyjnym wywołaniu algorytmu na odpowiednim zbiorze. Algorytm magicznych piątek dąży do znajdowania takiego elementu, który umożliwi podział zbioru A na stosunkowo równe zbiory: A< i A>.
Algorytm
Algorytm jest rekurencyjny. Dzielimy zbiór A na piątki liczb (przy czym ostatnia piątka może być niepełna) i dla każdej z piątek wybieramy medianę, co oznaczamy jako A5. Następnie rekurencyjnie wywołujemy algorytm magicznych piątek dla pary ⟨A5, ⌊|A5|/2⌋⟩, co oznacza, że szukamy mediany w zbiorze A5, niech wynikiem będzie m5.
Liczba m5 stanowi dobry punkt do wykonania podziału. W zbiorze A, w każdej piątce, której reprezentant okazał się mniejszy lub równy m5, przynajmniej połowa (a zazwyczaj trzy piąte) elementów jest nie większa od m5. W związku z tym przynajmniej jedna czwarta liczb ze zbioru A jest nie większa od m5, a analogicznie można wykazać, że przynajmniej jedna czwarta jest nie mniejsza.
W rezultacie dokonujemy podziału zbioru A na liczby mniejsze od m5 (zbiór A<), równe m5 (zbiór A=) oraz większe od niej (zbiór A>). Jeśli k jest mniejsze lub równe liczbie elementów w zbiorze A<, to rekurencyjnie wywołujemy algorytm dla ⟨A<, k⟩. W przeciwnym razie, jeśli k jest mniejsze lub równe sumie liczby elementów w zbiorach A< i A=, to zwracamy m5 jako k-tą liczbę. Jeśli nie, to wywołujemy rekurencyjnie algorytm dla ⟨A>, k – |A<| – |A=|⟩.
Analiza złożoności
Niech T(n) oznacza złożoność czasową algorytmu. Wykonanie algorytmu składa się z trzech kroków: znajdowania median piątek, co trwa Θ(n), wybierania (rekurencyjnie) mediany zbioru A5, co trwa T(n/5), oraz wywołania rekurencyjnego, które trwa co najwyżej T(max(|A<|, |A>|)).
Jak wcześniej wskazano, max(|A<|, |A>|) ≤ 3n/4, w związku z czym możemy oszacować czas wykonania całego algorytmu przez sumę maksymalnych czasów wykonania poszczególnych kroków, co daje nierówność:
T(n) ≤ Θ(n) + T(n/5) + T(3n/4).
Stosując standardowe metody rozwiązywania nierówności asymptotycznych (kluczowe jest, że 1/5 + 3/4 = 19/20 < 1), otrzymujemy, że algorytm magicznych piątek jest liniowy nawet w pesymistycznym przypadku.
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].
