Algorytmy i struktury danych/Selekcja

Selekcja

Rozważmy następujący problem:

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

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

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

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 $O(n\log n)$.

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 pierszej części tablicy: A[1..r] zostają przeniesione elementy o wartościach mniejszych lub równych m. W 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ń rekrurencyjnych (jak to było w przypadku algorytmu QuickSort), wykonać jedynie 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

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

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: $P_1,\dots ,P_{n/5}$
     (jeśli n nie jest wielokrotnością 5, to uzupełnij ostatni podciąg wartościami $+\mathrm{\infty }$)
     Niech $M=\{P_i[3]:1\le i\le n/5\}$ (zbiór median ciągów $P_i$);
     m:=AlgorytmMagicznychPiatek(M, $\lceil |M|/2\rceil$);
     $A_{<}:=\{A[i]:A[i]<m\}$;
     $A_{=}:=\{A[i]:A[i]=m\}$;
     $A_{>}:=\{A[i]:A[i]>m\}$;
     if $|A_{<}|\le k$ then
       return AlgorytmMagicznychPiatek($A_{<}$, k)
     else if $|A_{<}|+|A_{=}|\le k$
       return m
     else
       return AlgorytmMagicznychPiatek($A_{>}$, $k-|A_{<}|+|A_{=}|$);
  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 $O(n)$ krokach.

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

$T(n)=O(n)+T(|M|)+max(T(|A_{<}|),T(|A_{>}|))$

• rozmiar zbioru |M| możemy ograniczyć przez $\lceil n/5\rceil$
• ze względu na dodatkowy czas poświęcony na obliczanie mediany m, możemy podać lepsze ograniczenia na rozmiary zbiorów $A_{<},A_{>}$:

$0\le A_{<},A_{>}\le n-3\cdot \lfloor |M|/2\rfloor \le 3n/4$

$T(n)\le O(n)+T(n/5)+T(3n/4)$

---

powrót do wykładu