Algorytmy

Algorytmy

wyszukiwania

wyszukiwania

Beata Laszkiewicz

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”

)

(

)

(

n

cg

n

f



gdy dla dostatecznie dużych n istnieje

c>0, taka że

))

(

(

)

(

n

g

O

n

f



Najprostsza definicja:

Przeszukiwanie

Przeszukiwanie

liniowe

liniowe

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)

Przykład: Szukanie lidera w zbiorze

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.

Algorytm

składa się z dwóch części:

• szukamy kandydata na lidera,
• sprawdzamy, czy znalezniony kandydat

jest liderem zbioru.

Dane:

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

1

,

x

2

, ..., x

n

}

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

1

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

i

c:=1
else
if (x

i

=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)

Przeszukiwanie

Przeszukiwanie

binarne

binarne

Wielokrotnie rozwiązujemy problemy

następująco:

• podziel problem na podproblemy
• znajdź rozwiązania podproblemów,
• połącz rozwiązania podproblemów w

rozwiązanie głównego problemu.

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

• wykorzystuje strukturę zbioru: dane są

uporządkowane

• wykorzystuje metodę dziel i zwyciężaj
• Liczba elementów w zbiorze

przeszukiwanym jest połową (jest

zmniejszana) w każdym kroku algorytmu

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

Algorytm iteracyjny

left:=1
right:=n
s:= (left+right)/2
while (left<=right) and (t[s]!=y) do

if (t[s]<y) then left:=s+1
else right:=s-1
s:=(left+right)/2

if (left>right) then s:=-1

Algorytm rekurencyjny

search(left,right)

if (left>right) then return –1
else
s:=(left+right)/2
if (t[s]=y) then return s
else
if (t[s]<t) then search(s+1,right)
else search(left, s-1)

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

2

n

razy.

Złożoność algorytmu:

O(log

2

n)

Przeszukiwanie

Przeszukiwanie

interpolacyjne

interpolacyjne

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:

)

(

2

1

2

:

left

right

left

right

left

s











)

(

]

[

]

[

]

[

:

left

right

left

t

right

t

left

t

y

left

s











Algorytm przeszukiwania

interpolacyjnego

Złożoność algorytmu:

O(log

2

(log

2

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

2

n)

• Przeszukiwanie interpolacyjne

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

szukamy

 złożoność O(log

2

(log

2

n))

Dziękuję za uwagę!

Beata Laszkiewicz