Algorytmy i struktury danych/Selekcja

Selekcja

Rozważmy następujący problem:

Dany jest zbiór $A$ składający się z $n$ liczb oraz liczba $k$. Należy wyznaczyć $k$-ty co do wielkości element zbioru $A$, tzn. takie $a\in A$, że $|\{x\in A:x<a\}|=k-1$.

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

Możemy zauważyć, że szybkie (np. o złożoności $O(n)$) znajdowanie mediany pozwoliłoby 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 wskazanie k-tego elementu. Takie postępowanie wymaga czasu $\mathrm{\Omega }(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 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\le 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 Hoare'a

1  function AlgHoara(A[1..n],k);
2  begin
3   if n=1 and k=1 then return A[1]; 
4   // Partition
5   m:=A[1]; l:=1; r:=n;
6   while(l<r) do begin
7     while (A[l]<m) do l++;
8     while (m<A[r]) do r--;
9     if (l<=r) then begin
10      tmp:=A[l]; A[l]:=A[r]; A[r]:=tmp;
11      l++; r--;
12    end;
13  end;
14  if (k<=r) then 
15    return AlgHoara(A[1..r],k)
16  else
17    return AlgHoara(A[r+1..n],k-r)
18 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).

Algorytm magicznych piątek

Algorytm Hoare'a w pesymistycznym przypadku może wymagać bardzo długiego czasu działania. Możemy tak zmodyfikować poprzedni algorytm, aby zapewnić liniowy czas działania nawet w najgorszym przypadku.

Kluczem do nowego algorytmu jest lepszy wybór elementu dzielącego (zmienna m z 5-linii algorytmu Hoare'a). Element ten jest obliczany w następujący sposób:

• dzielimy ciąg $A$ na podciągi 5-elementowe $P_1,\dots ,P_{\lceil |A|/5\rceil }$,
  
  

---

---

• każdy z podciągów sortujemy, otrzymując $P{\text{'}}_1,\dots ,P{\text{'}}_{\lceil |A|/5\rceil }$,,
• wybieramy z każdego podciągu 3-ci co do wielkości element otrzymując krótszy ciąg $M$,
  
  

---

---

• jako m wybieramy medianę ciągu $M$ (którą to obliczamy rekrurencyjnie).

Dzięki takiemu znacznie bardziej skomplikowanemu wyborowi możemy zagwarantować bardziej równomierny podział ciągu $A$ na podciągi elementów mniejszych ($A_{<}$), oraz większych ($A_{>}$) od m.

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, 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. Nowy algorytm jest jednak 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 strony przedmiotu