Algorytmy i struktury danych/Selekcja

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Selekcja

Rozważmy następujący problem:

Dany jest zbiór składający się liczb oraz liczba . Należy wyznaczyć -ty co do wielkości element zbioru .

Dla niektórych wartości (np. 1 lub n) problem jest bardzo prosty i wymaga jedynie wyznaczenia minimalnej lub maksymalnej wartości, co możemy zrobić w czasie . Znacznie ciekawszym problemem jest np. znajdowanie mediany czyli -tego co do wielkości elementu - tu niestety problem jest bardziej skomplikowany.

Możemy zauważyć, że szybki (np. o złożoności ) algorytm znajdujący medianę pozwoliłoby tak poprawić algorytm sortowania QuickSort, żeby nawet w pesymistycznym przypadku działał w czasie .

Najprostszym rozwiązaniem naszego problemu może być uporządkowanie zbioru, np. algorytmem MergeSort, i zwrócenie k-tego elementu. Takie postępowanie wymaga czasu .

Jednak można łatwo zauważyć, że nasz problem jest znacznie prostszy od problemu sortowania. Czy można rozwiązać go szybciej? Okazuje się, że jest to możliwe; w następnej części wykładu przedstawimy dwa algorytmy, które rozwiązują nasz problem znacznie sprytniej.


Algorytm Hoare'a

Algorytm jest oparty na tym samym pomyśle, co algorytm sortowania QuickSort.

Dla danej tablicy A[1..n] oraz liczby k, algorytm wybiera element dzielący m (np. pierwszy element z tablicy), a następnie używa go do podzielenia tablicy na dwie części. Do pierwszej części tablicy - A[1..r] - zostają przeniesione elementy o wartościach mniejszych lub równych m. Do drugiej części (A[r+1..n]) - elementy o wartościach większych lub równych m.

Ponieważ naszym zadaniem jest jedynie wyznaczenie k-tego co do wielkości elementu tablicy, możemy zamiast 2 wywołań rekurencyjnych (jak to było w przypadku algorytmu QuickSort), wykonać tylko jedno wywołanie rekurencyjne.

Jeśli k<=r, to poszukiwana wartość znajduje się w pierwszej części tablicy, wpp. możemy zawęzić poszukiwania do drugiej części tablicy, jednak zamiast wyszukiwać k-tej wartości musimy poszukiwać (k-r)-tej wartości.

Algorytm

function AlgHoara(A[1..n],k);
begin
  if n=1 && k=1 then return A[1];

  // Partition
  m:=A[1]; l:=1; r:=n;
  while(l<r) do begin
    while (l<n && A[l]<m) do l++;
    while (r>1 && A[r]>m) do r--;
    if (l<=r) then begin
      tmp:=A[l]; A[l]:=A[r]; A[r]:=tmp;
      l++; r--;
    end;
  end;

  // TODO, sprawdzić czy nie ma błędów     
  if (r<=k) then 
    return AlgHoara(A[1..r],k)
  else
    return AlgHoara(A[r+1..n],k-r)
end;

Analiza algorytmu

Niestety, w pesymistycznym przypadku ten algorytm może zachowywać się bardzo źle. Dla uporządkowanego ciągu i k=n, czas działania algorytmu wynosi O(n^2). Jednak tak jak w przypadku algorytmu QuickSort, w średni koszt działania algorytmu jest znacznie lepszy i wynosi O(n).


  • TODO -- dodać kod programu z implementacją

Algorytm magicznych piątek

podział na podciągi 5-elementowe

Selekcja.1.png

wybór zbioru M - zbioru median podciągów

Selekcja.2.png

Algorytm

function AlgorytmMagicznychPiatek(A[1..n], k);
begin
  if n<=10 then
     posortuj tablicę A
     return A[k]
  else begin
     podziel elementy z tablicy A na podciągi 5-elementowe: 
     (jeśli n nie jest wielokrotnością 5, to uzupełnij ostatni podciąg wartościami )
     Niech  (zbiór median ciągów );
     m:=AlgorytmMagicznychPiatek(M, );
     ;
     ;
     ;
     if  then
       return AlgorytmMagicznychPiatek(, k)
     else if 
       return m
     else
       return AlgorytmMagicznychPiatek(, );
  end
end

Analiza złożoności czasowej

Na pierwszy rzut oka, algorytm wygląda bardzo podobnie do algorytmu Hoare'a. Jednak nowy algorytm jest znacznie bardziej efektywny: nawet w pesymistycznym przypadku algorytm kończy działanie po krokach.

Złożoność algorytmu możemy opisać następującym równaniem rekurencyjnym.

  • rozmiar zbioru |M| możemy ograniczyć przez
  • ze względu na dodatkowy czas poświęcony na obliczanie mediany m, możemy podać lepsze ograniczenia na rozmiary zbiorów :

Selekcja.3.png


powrót do strony przedmiotu