Algorytm Floyda-Rivesta

Floyd-Rivest
Klasa	Algorytm wyboru
Struktura danych	Szyk
Średnia wydajność	n + min( k , n - k ) + O ( n 1/2 log 1/2 n )

W informatyce algorytm Floyda-Rivesta to algorytm selekcji opracowany przez Roberta W. Floyda i Ronalda L. Rivesta , który ma optymalną oczekiwaną liczbę porównań w terminach niższego rzędu . Funkcjonalnie jest odpowiednikiem quickselect , ale w praktyce działa średnio szybciej. Ma oczekiwany czas działania $O (n)$ i oczekiwaną liczbę porównań $n + min (k, n - k) + O (n 1/2 log 1/2 n)$ .

Algorytm został pierwotnie przedstawiony w raporcie technicznym Uniwersytetu Stanforda, zawierającym dwa artykuły, w których był określany jako SELECT i sparowany z PICK, czyli medianą median . Został on następnie opublikowany w Communications of the ACM , tom 18: wydanie 3.

Algorytm

Algorytm Floyda-Rivesta to algorytm typu „dziel i rządź” , który ma wiele podobieństw z algorytmem quickselect . Wykorzystuje próbkowanie , aby pomóc podzielić listę na trzy zestawy. Następnie rekurencyjnie wybiera k- ty najmniejszy element z odpowiedniego zestawu.

Ogólne kroki to:

Wybierz małą losową próbkę S z listy L .
Z S , rekurencyjnie wybierz dwa elementy, u i v , takie, że u < v . Te dwa elementy będą osiami podziału i oczekuje się, że będą zawierały k- ty najmniejszy element całej listy między nimi (na posortowanej liście).
Używając u i v , podziel S na trzy zbiory: A , B i C . A będzie zawierać elementy o wartościach mniejszych niż u , B będzie zawierało elementy o wartościach od u do v , a C będzie zawierało elementy o wartościach większych niż v .
Podziel pozostałe elementy w L (czyli elementy w L - S ) porównując je z u lub v i umieszczając je w odpowiednim zestawie. Jeśli k jest mniejsze niż połowa liczby elementów w L zaokrąglonych w górę, to pozostałe elementy należy porównać najpierw z v , a dopiero potem z u , jeśli są mniejsze niż v . W przeciwnym razie pozostałe elementy należy porównać najpierw z u i dopiero z v , jeśli są większe od u .
Na podstawie wartości k zastosuj algorytm rekurencyjnie do odpowiedniego zbioru, aby wybrać k-ty najmniejszy element w L .

Używając | S | = Θ( n ^2/3 log ^1/3 n ), możemy otrzymać $n + min(k, n - k) + O (n 2/3 log 1/3 n)$ oczekiwanych porównań. Możemy uzyskać $n + min(k, n - k) + O (n 1/2 log 1/2 n)$ , zaczynając od małego S i wielokrotnie aktualizując u i v , aby rozmiar B był wystarczająco mały ( O ( n ^1/2 log ^1/2 n ) przy Θ ( n ) przetworzonych elementów) bez niedopuszczalnego ryzyka, że pożądany element znajdzie się poza B .

Wersja pseudokodu

Poniższy pseudokod przestawia elementy między left i right , tak że dla pewnej wartości k , gdzie left ≤ k ≤ right , k -ty element na liście będzie zawierał ( k − left + 1)-tą najmniejszą wartość, z i-tym elementem jest mniejszy lub równy k th dla wszystkich lewych ≤ i ≤ k i j-ty element jest większy lub równy dla k ≤ j ≤ prawy :


      
        
            
            
            
         //  lewy jest lewym indeksem przedziału  //  prawy jest prawym indeksem przedziału  //  k jest żądaną wartością indeksu, gdzie array[k] jest (k+1)-tym najmniejszym elementem, gdy left = 0  funkcja  select (array, left, right, k)  to  while  right  >  left  do  //  Użyj rekursywnie selekcji do próbkowania mniejszego zestawu o rozmiarze s  //  dowolne stałe 600 i 0,5 są używane w oryginalnej wersji   //  w celu zminimalizowania czasu wykonania.  jeśli  prawy − lewy > 600  to  n := prawy − lewy + 1 i := k − lewy + 1 z :=  ln  (n) s := 0,5 ×  exp  (2 × z/3) sd := 0,5 ×  sqrt  ( z × s × (n − s)/n) ×  znak  (i − n/2) nowyLewy :=  max  (lewy, k − i × s/n + sd) nowyPrawy :=  min  (prawy, k + (n − i) × s/n + sd)  select  (array, newLeft, newRight, k) //  podziel elementy pomiędzy lewe i prawe wokół t  t := array[k] i := left j := right  zamień  array[left] i tablica[k]  jeśli  tablica[prawa] > t  to  zamień tablicę   [  prawą] i tablicę[lewą]  podczas gdy  i < j  zamień  tablicę[i] i tablicę[j] i := i + 1 j := j − 1  while  tablica[i] < t  do  i := i + 1  while  tablica[j] > t  do  j := j − 1  if  tablica[lewo] = t  to  zamień  tablicę[lewo] i tablicę[j]  else  j := j + 1  zamiana  tablica[j] i tablica[prawo] //  Dopasowanie lewej i prawej strony do granic podzbioru  //  zawierającego (k − lewy + 1) najmniejszy element.  jeśli  j ≤ k  to  w lewo := j + 1  jeśli  k ≤ j  to  w prawo := j − 1

Zobacz też

Floyd, Robert W .; Rivest, Ron L. (marzec 1975). „Oczekiwane granice czasowe wyboru” (PDF) . Komunikaty ACM . 18 (3): 165–172. doi : 10.1145/360680.360691 .
Kiwiel, Krzysztof C. (30 listopada 2005). „O algorytmie SELECT Floyda i Rivesta” (PDF) . Informatyka teoretyczna . 347 (1–2): 214–238. doi : 10.1016/j.tcs.2005.06.032 .
Gerbessiotis, Alexandros V.; Siniolakis, Constantinos J.; Paraskevi, Aghia (maj 2005). „Analiza probabilistyczna algorytmu wyboru oczekiwanego czasu Floyda-Rivesta”. International Journal of Computer Mathematics . 82 (5): 509–519. CiteSeerX 10.1.1.7.8672 .