Uniwersytet Śląski

Wydział Informatyki i Nauki o Materiałach

Paweł Grzesica

Nr albumu: 251956

Analiza i złożoność obliczeniowa algorytmów

Wyszukiwanie binarne(połówkowe) oraz drzewa poszukiwań binarnych (BST)

Sosnowiec, 2013

Spis treści

1. Pojęcie wyszukiwania

Algorytm jest ciągiem kroków obliczeniowych, mającym na celu przekształcenie danych wejściowych w wyjściowe. Jest on więc rozwiązaniem konkretnego problemu obliczeniowego. W zależności od potrzeb istnieją różne typy algorytmów, jak algorytm sortowania, selekcji, wstawiania, usuwania etc.

Algorytm wyszukiwania jest jednym z najczęściej stosowanych. Wyszukiwanie jest sposobem, za pomocą którego przeszukuje się zbiór danych (najczęściej w postaci tablicy) w celu znalezienia wymaganych zmiennych.

Istnieje wiele algorytmów wyszukiwania :

• wyszukiwanie liniowe,

• wyszukiwanie liniowe z wartownikiem,

• wyszukiwanie linowe w posortowanej tablicy,

• wyszukiwanie binarne (połówkowe/logarytmiczne),

• drzewa przeszukiwań binarnych (BST),

• haszowanie.

Uwaga w niniejszej pracy zostanie poświęcona wyszukiwaniu binarnemu (połówkowemu) oraz drzewom przeszukiwań binarnych (BST). Oba wyszukiwania oparte są na metodzie „dziel i zwyciężaj” (rekurencja opierająca się na podziale jednego poziomu rekursji na trzy etapy).

2. Wyszukiwanie binarne

2.1. Pojęcie i algorytmy wyszukiwania binarnego

Szukanie binarne, zwane również połówkowym, jest szybką metodą wyszukiwania elementów w czasie logarytmicznym w posortowanych tablicach, skąd bierze swoją nazwę. W przypadku znalezienia szukanej podaje jej indeks w tablicy. Sortowanie może być dowolne, w zależności od wymagań: rosnące, malejące etc.

Rozpoczęcie przeszukiwania tablic rozpoczyna się w momencie dzielenia na coraz mniejsze podtablice. Algorytm rozpoczyna swoje działanie od przeszukania całej tablicy. W pojedynczym kroku wyszukuje się indeksy początkowy i końcowy. Po wyznaczeniu środka przedziału tych indeksów, sprawdzana jest jego poprawność – gdy indeks środkowy jest poszukiwanym, algorytm kończy działanie. W przeciwnym wypadku algorytm sprawdza położenie poszukiwanej wartości i, w zależności od tego, czy znajduje się ona bliżej początku (lewej części badanej tablicy) czy końca indeksu (prawej strony badanej tablicy), procedura jest powtarzana od nowa.

Przykładowy algorytm wyszukiwania binarnego:

procedure wyszukiwanie binarne(x: typ klucza;

var jest: Boolean ;

var m: 1 .. n);

var lewy, prawy: 0 .. n + 1;

begin

lewy := 1; prawy := n; jest := false ; repeat

m := (lewy + prawy) div 2;

if A[m].klucz = x then

jest := true ;

else

if A[m].klucz < x then

lewy := m + 1;

else

prawy := m − 1;

end if;

end if;

until jest or (lewy > prawy);

end; {wyszukiwanie binarne}

2.2. Złożoności obliczeniowe

Złożoność obliczeniowa pozwala oszacować czas potrzebny do wykonania algorytmu. Złożoność tę wyznacza zależność czasu potrzebnego do wykonania algorytmu od rozmiaru danych wejściowych (najczęściej jest to ich ilość). Na złożoność obliczeniową algorytmu składa się złożoność czasowa i złożoność pamięciowa. W przypadku algorytmów można wyróżnić kilka rodzajów złożoności matematycznych:

* stała,

* logarytmiczna,

* liniowa,

* liniowo-logarytmiczna,

* kwadratowa,

* wykładnicza.

Złożoność czasowa jest zależnością pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu, a rozmiarem danych wejściowych. Wynika z liczby operacji elementarnych wykonywanych w trakcie przebiegu algorytmu i decyduje o tym, czy dany algorytm jest przydatny. O złożoności czasowej decyduje liczba wykonywanych iteracji

Całkowity koszt czasowy wynosi

T(N) = K1 + max( K3,K4) + K2 * lg N

W przypadku wyszukiwania binarnego złożoność obliczeniowa czasowa jest logarytmiczna i wynosi

T(N) = O (log n),

co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób logarytmiczny wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. Zapis T(N) = O(f(n)) oznacza, że istnieją takie stałe dodatnie c oraz n₀, że dla każdego n >= n₀ zachodzi T(N) <= cf(n) T_W(n) <= T_A(n). Algorytm ten jest więc bardzo szybki. Logarytmiczna złożoność jest osiągana dzięki temu, że każde wykonane porównanie zmniejsza o połowę przedział, w którym może znajdować się szukana wartość.

Złożoność pamięciowa jest to cecha algorytmu, która wynika z liczby i rozmiaru struktur danych wykorzystywanych w algorytmie. Złożoność ta wyznacza zależność rozmiaru pamięci potrzebnej do realizacji algorytmu od wielkości danych wejściowych. Ten sam algorytm uruchomiony jako program na komputerach o różnych konfiguracjach może wymagać różnej wielkości pamięci. Złożoność pamięciowa jest najczęściej proporcjonalna do liczby zmiennych użytych w algorytmie. Określa ona więc ilość pamięci, którą potrzebuje algorytm na rozwiązanie problemu. Dla wyszukiwania binarnego złożoność pamięciowa wynosi O (1). Oznacza to, że algorytm zużywa stałą liczbę komórek pamięci bez względu na rozmiar danych n. Czas wykonania jest stały i nie zmienia się przy zmianie liczby przetwarzania elementów.

Rozróżnia się dwa rodzaje czasowej i pesymistycznej złożoności obliczeniowej:

• Pesymistyczna złożoność obliczeniowa – określa największą ilość operacji dominujących (lub komórek pamięci), która może być wymagana dla najgorszego przypadku n danych wejściowych, dotyczy najgorszego zestawu danych. Przez pesymistyczną złożoność czasową algorytmu rozumie się funkcję:

T_W(n) = sup {t(d): d należy do Dn}, gdzie sup oznacza kres górny zbioru. W najgorszym wypadku iteracja w algorytmie jest powtarzana 1+ log₂ N (= log N). Zatem pesymistyczna złożoność algorytmu wyszukiwania binarnego wynosi:

T_W (n) = O (log n),

• Średnia (oczekiwana) złożoność obliczeniowa – jest to średnia wartość złożoności dla wszystkich problemów rozmiaru n. Określa statystycznie średnia ilość operacji dominujących (komórek pamięci), które należy wykonać dla typowego zestawu danych, aby rozwiązać problem. Przez średnią złożoność obliczeniową rozumie się funkcję T_A(n) = ∑ k×pn(k), gdzie pn (k) jest prawdopodobieństwem zdarzenia, że koszt t(d) dla danych d rozmiaru n jest k. Jest analizą najgorszego przypadku lub analizą średniego przypadku.?? (7)

T_A (n) = O (log n) ??

2.3. Schemat blokowy

Schemat blokowy jest jednym ze sposobów opisu algorytmu i zawiera plan algorytmu przedstawiony w postaci graficznej struktury elementów zwanymi blokami. Każdy blok zawiera informację o operacji, która ma być w nim wykonana, a pomiędzy blokami umieszczone są linie przepływu (strzałki) określające kolejność wykonywania bloków algorytmu.

3. Drzewa przeszukiwań binarnych

Drzewa binarne jest rodzajem struktury danych, w których liczba synów w każdym wierzchołku nie przekracza dwóch. Drzewa binarne zawierające w wierzchołku zero lub dwóch synów nosi nazwę drzewa regularnego. Szczególną odmianą drzew binarnych są drzewa przeszukiwań binarnych.

Drzewa przeszukiwań binarnych, w skrócie BST (z ang. binary search trees), są strukturami, na których można wykonywać różne operacje właściwe dla zbiorów dynamicznych, jak Search, ,Minimum, Maximum, Insert, Delete, etc. Drzewa te są więc zarówno słownikiem jak i kolejką priorytetową.

O czasie operacji wykonywanych na drzewach decyduje ich wysokość.

Bibliografia:

1. Bałachowski L., Diks K., Rytter W., „Algorytmy i Struktury Danych”, WNT, Warszawa 1996.

2. Carmen T.H., Leiserson C.E., Rivest R.L., Stein C., „Wprowadzenie do algorytmów“, WNT, Warszawa 1997,2001.

3. Czech Z.J., „Algorytmy i struktury danych, materiały dydaktyczne”.

4.

5. http://we.pb.edu.pl/~jforenc/inf1-dzienne/INF1-2013-Wykl-07-Dzienne.pdf

6. http://www.cs.put.poznan.pl/akobusinska/downloads/wprowadzenie/w5-obliczalnosc_zlozonosc.pdf

7. http://oxygene.ibspan.waw.pl/~sikorski/wi/wi_mpd06.pdf