Searching algorithms

Streszczenie

1. Użyteczna notacja

 Złożoność - powtórzenie
 Notacja O

2. Przeszukiwanie liniowe

 Znaczenie, zastosowania
 Przykłady algorytmów (kilka klasycznych i innych)

3. Przeszukiwanie binarne

 Teoretyczny punkt widzenia
 Przykład

4. Przeszukiwanie interpolacyjne

Wielkość opisująca największą liczbę

kosztownych operacji wykonywanych

przez algorytm dla dowolnego układu

danych.

Złożoność może być pesymistyczna,

optymalna, ….

Złożoność algorytmu

Notacja

Notacja ”O”

)

(

)

(



gdy dla dostatecznie dużych n istnieje

c>0, taka że

))

(

)

(



Najprostsza definicja:

Przeszukiwanie liniowe

• Jest sprawdzeniem zbioru element po

elemencie (w kolejności takiej, jak

elementy są przechowywane w zbiorze)

• Używamy, gdy nie mamy żadnych

dodatkowych informacji o (np. że jest

to zbiór uporządkowany)

Przeszukiwanie liniowe

może być

użyte do rozwiązania następujących

problemów:

 szukanie min elementu w zbiorze

szukanie max elementu w zbiorze
Szukanie zadanego elementu w

zbiorze (nieuporządkowanym)

wyszukiwanie lidera w zbiorze

Dane:

t - zbiór n elementowy

(przechowywany w tablicy)

Wynik:

min element z tego zbioru

min:=t[1]
for i:=2, 3, ..., n do
if (t[i]<min) then min:=t[i]

Przykład: Szukanie min w zbiorze

Złożoność algorytmu:

O(n)

elementem, który występuje w zbiorze

Więcej niż połowę razy (więcej niż n/2 razy)

n jest liczbą elementów zbioru

• Zbiór {1, 2, 1, 3, 1, 4} nie ma lidera,

ponieważ 1 występuje dokładnie 3 = 6/2
razy.

• Zbiory {1, 2, 1, 3, 1, 1} oraz {1, 2, 1, 3, 1, 4,

1} mają lidera. W ostatnim zbiorze częstość
występowania lidera jest równa 4, co jest
większe niż 7/2.

Lider w zbiorze jest

Zastosowanie w codziennym życiu

(Polska)

• Podczas wyborów prezydenta zwycięzcą jest

ten, który otrzyma więcej niż 50% głosów.

• Jeśli jest 2 lub 3 kandydatów, najłatwiejszą

metodą liczenia głosów jest rozłożenie ich na
stosy związane z nazwiskami kanadydatów.

• Niestety obecnie zazwyczaj jest więcej

kandydatów (nawet do 17), więc byłoby
dobrze mieć inną metodę, która jest w
pewnym sensie szybsza.

Inne metody

• znajdź element, który jest naczęściej

występującym elementem (

modalna

) i

sprawdź, czy występuje więcej niż n/2 razy,

• znajdź

medianę

(środkowy element zbioru

uporządkowanego, na pozycji n/2) i sprawdź,
czy jest liderem (ponieważ jeśli zbiór ma
lidera, to jest on jego medianą)

• Inny, bardziej elegancki sposób znajdowania

lidera w zbiorze.

Co jest nie tak z 2 wspomnianymi

metodami?

• Jeśli chcemy znaleźć

modalną

musimy

posortować elementy zbioru, co jest

pracochłonne, szczgólnie dla dużych n.

Najszybszy algorytm sortowania

wykonuje wiele kosztownych operacji

• Istnieje algorytm szukania

mediany

bez

sortowania, ale jest skomplikowany.

Elegancki sposób

Ostatnia metoda jest bardzo
elegancka, ponieważ wykorzystuje
pewną „zaskakującą” obserwację:

Jeżeli zbiór X zawiera lidera,

a x oraz y są jego różnymi

elementami,

wtedy zbiór Y=X-{x,y} również

zawiera lidera.

Inaczej ujmując:

X ma lidera => Y=X-{x,y} ma lidera,

dla x, y – różnych elementów

Uwaga:

Przciwne twierdzenie nie jest prawdziwe,
tzn. zredukowany zbiór Y może zawierać
lidera, choć zbiór X go nie posiada!

Dowód obserwacji: (bardzo prosty)

Niech l oznacza lidera zbioru X. Jeśli x
oraz y są

różnymi elementami

X, wtedy

co najwyżej jeden z nich jest równy l,
zatem w zredukowanym zbiorze Y liczba
elementów jest o 2 mniejsza, a częstość
występowania l jest co najwyżej o 1
mniejsza, więc l jest nadal liderem w
zbiorze Y.

Musimy jedynie sprawdzić, czy lider
zbioru Y jest liderem zbioru
początkowego.

Dane:

X – zbiór składający się z n elementów {x

, ..., x

}

Wynik:

l – lider zbioru lub informacja, że zbiór ne

ma lidera

l

oznacza kandydata na lidera.

c oznacza niejako liczbę wystąpień kandydata,
obliczaną przez porównania w algorytmie. Inaczej
mówiąc ta liczba odpowiedzialna jest za usuwanie par
elementów ze zbioru.

Specyfikacja

l:=x

c:=1
for i:=2, 3, ..., n do
if (c=0) then
l:=x

      c:=1
   else
      if (x

=l) then c:=c+1

else c:=c-1

wybieramy nowego kandaydata na lidera

porównujemy kolejny element z kandaydatem,

jeśli element nie jest równy liderowi,

usuwamy go z jednym wystąpieniem kandyadta na lidera.

CZĘŚĆ 1:

CZĘŚĆ 2:

• if (c=0) then zbiór nie ma lidera i zakończ

alg.

• if (c>0) then

znajdź k – liczbę wystąpień kandydata w

zbiorze

if (k>n/2) then l jest liderem w zbiorze

X, else zbiór X nie ma lidera i zakończ.

Złożoność algorytmu

• W części pierwszej mamy (n-1)

porównań

• W części drugiej mamy 1+ (n+1)

porównań

• Liczba porównań jest równa 2n+1 = O(n)

Dla porównania, najszybszy algorytm

sortowania ma złożoność

O(n log n)

Aby być efektywnym,

potrzebujemy dodatkowych

warunków:

• Problem jest dzielony na takie same lub bardzo

podobne podproblemy (zazwyczaj podproblemy

są takie same: rekurencja)

• Liczba podproblemów jest równa co najmniej 2
• Podproblemy są rozwiązywane na podzbiorach

zbioru danych, w których liczba elementów jest

niemal jednakowa i stanowi stałą cześć (np.

połowę) całego zbioru danych rozwiązywanego

problemu

Metoda dziel i zwyciężaj

Przeszukiwanie binarne -

algorytm

Dane:

t – zbiór n elementowy

y – element, którego szukamy

Wynik:

s, 1<=s<=n, taki że t[s]=y lub

s = -1, jeśli element y nie występuje

w zbiorze t

Złożoność algorytmu

Odpowiedź na pytanie o liczbę

podziałow zbioru w najgorszym

przypadku tzn.

Jak wiele razy musimy odrzucać połowę

aktualnego zbioru, aby otrzymać jeden

element?

Zbiór n elementowy może być
połowiony co najwyżej

log

razy.

Złożoność algorytmu:

O(log

Przeszukiwanie

interpolacyjne

• Przeszukiwanie binarne może nie być tak

szybki, jak byśmy oczekiwali; przykład:

”nazwisko na B” w książce telefonicznej

• Jak szukamy:
Przeszukiwanie binarne:

porównujemy

czy

y jest większy, mniejszy czy

równy elementowi zbioru

Przeszukiwanie interpolacyjne:

Sprawdzamy i korzystamy z informacji

jak

bardzo

y jest większy, mniejszy od elementu w

zbiorze

Dzielimy zbiór danych, ale próbujemy strzelić

bliżej części zbioru, którą jesteśmy

zainteresowani

Porównanie

Przeszukiwanie binarne:

Przeszukiwanie interpolacyjne:

)

(

left

right

left

right

left











)

(

]

[

]

[

]

[

left

right

left

right

left







Algorytm przeszukiwania

interpolacyjnego

Złożoność algorytmu:

O(log

(log

n))

Dane, wyniki:

jak w przeszukiwaniu binarnym

Metoda:

jak w przeszukiwaniu binarnym, z

wyjątkiem obliczania s

Uwaga:

w praktyce komputerowa realizacja

przeszukiwania interpolacyjnego nie wygrywa z
przeszukiwaniem binarnym:

• dla małych n liczba log n jest mała
• Inne operacje zwiększają łączną liczbę

operacji

Podsumowanie:

• Przeszukiwanie liniowe

 łatwe do użycia dla wielu problemów
 dla zbiorów nieuporządkowanych
 złożoność O(n)

• Przeszukiwanie binarne

 dla zbiorów uporządkownych
 wykorzystuje metodę dziel i zwyciężaj
 złożoność O(log

• Przeszukiwanie interpolacyjne

 dla zbiorów uporządkowanych
 wykorzystuje informację o elemencie, którego

szukamy

 złożoność O(log

(log

n))

Document Outline