Algorytmy i struktury danych/Selekcja: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 9: Linia 9:
 
jedynie wyznaczenia minimalnej lub maksymalnej wartości, co możemy zrobić w czasie <math>O(n)</math>.
 
jedynie wyznaczenia minimalnej lub maksymalnej wartości, co możemy zrobić w czasie <math>O(n)</math>.
 
Znacznie ciekawszym problemem jest np. znajdowanie mediany czyli  
 
Znacznie ciekawszym problemem jest np. znajdowanie mediany czyli  
<math>\frac{n}{2}</math>-tego co do wielkości elementu,
+
<math>\frac{n}{2}</math>-tego co do wielkości elementu -
 
tu niestety problem jest bardziej skomplikowany.
 
tu niestety problem jest bardziej skomplikowany.
  
Możemy zauważyć, że szybki (np. o złożoności <math>O(n)</math>) algorytm znajdujący medianę,
+
Możemy zauważyć, że szybki (np. o złożoności <math>O(n)</math>) algorytm znajdujący medianę
 
pozwoliłoby tak poprawić algorytm sortowania QuickSort, żeby nawet w pesymistycznym
 
pozwoliłoby tak poprawić algorytm sortowania QuickSort, żeby nawet w pesymistycznym
 
przypadku działał w czasie <math>O(n\log n)</math>.
 
przypadku działał w czasie <math>O(n\log n)</math>.
  
Najprostszym rozwiązaniem naszego problemu, może być uporządkowanie
+
Najprostszym rozwiązaniem naszego problemu może być uporządkowanie
zbioru, np. algorytmem MergeSort i zwrócenie k-tego elementu.
+
zbioru, np. algorytmem MergeSort, i zwrócenie k-tego elementu.
 
Takie postępowanie wymaga czasu <math>O(n\log n)</math>.
 
Takie postępowanie wymaga czasu <math>O(n\log n)</math>.
  
 
Jednak można łatwo zauważyć, że nasz problem jest znacznie prostszy od problemu sortowania.
 
Jednak można łatwo zauważyć, że nasz problem jest znacznie prostszy od problemu sortowania.
 
Czy można rozwiązać go szybciej?
 
Czy można rozwiązać go szybciej?
Okazuje się, że jest to możliwe, w następnej części wykładu przedstawimy dwa algorytmy,
+
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.
 
które rozwiązują nasz problem znacznie sprytniej.
  
Linia 34: Linia 34:
 
algorytm wybiera element dzielący ''m'' (np. pierwszy element z tablicy),
 
algorytm wybiera element dzielący ''m'' (np. pierwszy element z tablicy),
 
a następnie używa go do podzielenia tablicy na dwie części.
 
a następnie używa go do podzielenia tablicy na dwie części.
Do pierwszej części tablicy: ''A[1..r]'' zostają przeniesione elementy
+
Do pierwszej części tablicy - ''A[1..r]'' - zostają przeniesione elementy
 
o wartościach mniejszych lub równych ''m''.
 
o wartościach mniejszych lub równych ''m''.
W drugiej części (''A[r+1..n]'') - elementy o wartościach
+
Do drugiej części (''A[r+1..n]'') - elementy o wartościach
 
większych lub równych ''m''.
 
większych lub równych ''m''.
  
Ponieważ naszym zadaniem jest jedynie wyznaczenie ''k'' tego co do
+
Ponieważ naszym zadaniem jest jedynie wyznaczenie ''k''-tego co do
 
wielkości elementu tablicy, możemy zamiast 2 wywołań rekurencyjnych
 
wielkości elementu tablicy, możemy zamiast 2 wywołań rekurencyjnych
(jak to było w przypadku algorytmu QuickSort), wykonać jedynie
+
(jak to było w przypadku algorytmu QuickSort), wykonać tylko
 
jedno wywołanie rekurencyjne.
 
jedno wywołanie rekurencyjne.
  
 
Jeśli ''k''<=''r'', to poszukiwana wartość znajduje się w pierwszej części
 
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,
 
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.
+
jednak zamiast wyszukiwać ''k''-tej wartości musimy poszukiwać ''(k-r)''-tej wartości.
  
 
=== Algorytm ===
 
=== Algorytm ===
Linia 74: Linia 74:
 
=== Analiza algorytmu ===
 
=== Analiza algorytmu ===
  
Niestety w pesymistycznym przypadku ten algorytm może zachowywać się
+
Niestety, w pesymistycznym przypadku ten algorytm może zachowywać się
 
bardzo źle.
 
bardzo źle.
 
Dla uporządkowanego ciągu i ''k''=''n'', czas działania algorytmu wynosi ''O(n^2)''.
 
Dla uporządkowanego ciągu i ''k''=''n'', czas działania algorytmu wynosi ''O(n^2)''.
Linia 113: Linia 113:
 
         '''return''' m
 
         '''return''' m
 
       '''else'''
 
       '''else'''
         '''return''' AlgorytmMagicznychPiatek(<math>A_{>}</math>, <math>k-|A_{<}|+|A_=|</math>);
+
         '''return''' AlgorytmMagicznychPiatek(<math>A_{>}</math>, <math>k-|A_{<}|-|A_=|</math>);
 
   '''end'''
 
   '''end'''
 
  '''end'''
 
  '''end'''
Linia 120: Linia 120:
  
 
Na pierwszy rzut oka, algorytm wygląda bardzo podobnie do algorytmu Hoare'a.
 
Na pierwszy rzut oka, algorytm wygląda bardzo podobnie do algorytmu Hoare'a.
Jednak nowy algorytm jest znacznie bardziej efektywny, nawet w pesymistycznym  
+
Jednak nowy algorytm jest znacznie bardziej efektywny: nawet w pesymistycznym  
przypadku, algorytm kończy działanie po <math>O(n)</math> krokach.
+
przypadku algorytm kończy działanie po <math>O(n)</math> krokach.
  
 
Złożoność algorytmu możemy opisać następującym równaniem rekurencyjnym.
 
Złożoność algorytmu możemy opisać następującym równaniem rekurencyjnym.

Wersja z 12:40, 25 wrz 2006

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