Algorytmy i struktury danych - ebook

Przedmowa do pierwszego wydania

Niniejsza książka jest przeznaczona dla czytelników interesujących się głębiej informatyką, w tym przede wszystkim dla studentów informatyki. W szczególności może służyć jako podręcznik do wykładów: „Algorytmy i struktury danych” i „Analiza algorytmów” dla studentów studiów informatycznych. Jej fragmenty mogą być także wykorzystane w nauczaniu przedmiotów „Metody programowania” oraz „Kombinatoryka i teoria grafów” w ujęciu algorytmicznym. Sądzimy, że książka może też zainteresować szersze kręgi czytelników, gdyż daje elementarne wprowadzenie do nowoczesnych metod tworzenia i analizy algorytmów. Metody te oraz bogactwo różnorodnych struktur danych, przedstawionych w książce, mogą być pomocne w projektowantiu efektywnych algorytmów dla problemów pojawiających się w praktyce programistycznej lub pracy badawczej.

Zakładamy, że czytelnik ma pewne podstawowe przygotowanie z kombinatoryki i rachunku prawdopodobieństwa (na poziomie szkoły średniej) i że umie układać algorytmy w Pascalu. Znajomość przedmiotów: „Wstęp do informatyki”, „Metody programowania” i „Analiza matematyczna I” jest pożądana przy czytaniu tej książki, ale niekonieczna.

Książka powstała z notatek do wykładów: „Algorytmy i struktury danych” oraz „Analiza algorytmów” prowadzonych przez nas dla studentów informatyki Uniwersytetu Warszawskiego w latach 1986–1994. Pierwsza jej wersja ukazała się w postaci skryptu Uniwersytetu Warszawskiego .

Niniejsza książka składa się z 8 rozdziałów. Rozdział 1 stanowi wprowadzenie do dziedziny analizy algorytmów. Zdefiniowaliśmy w nim takie pojęcia, jak złożoność obliczeniowa i poprawność semantyczna algorytmu. Omówiliśmy rozwiązywanie równań rekurencyjnych oraz podstawowe struktury danych: listy, zbiory, grafy, drzewa i ich realizacje. Przedstawiliśmy także elementarne metody algorytmicznego rozwiązywania problemów. Rozdział 2 zawiera omówienie głównych algorytmów sortowania wraz z ich analizą i zastosowaniami wprowadzonych struktur danych do rozwiązywania pokrewnych problemów. Rozdział 3 jest poświęcony zadaniu wyszukiwania elementów w zbiorze. Przedstawiliśmy w nim podstawowe struktury danych i częściową ich analizę. W rozdziale 4 omówiliśmy i zanalizowaliśmy dwie złożone struktury danych, umożliwiające szybkie wykonywanie operacji na zbiorach rozłącznych. Opisaliśmy rozwiązanie problemu sumowania zbiorów rozłącznych i przedstawiliśmy implementację złączalnych kolejek priorytetowych za pomocą drzew dwumianowych. Rozdziały 5, 6, 7 i 8 są poświęcone zagadnieniom informatyki teoretycznej, w której badania nad algorytmami rozwijały się w ostatnich latach najszybciej. Przedstawiliśmy w nich algorytmy tekstowe, a także algorytmy równoległe, grafowe i geometryczne. Każdy rozdział jest zakończony zestawem zadań umożliwiających pogłębienie zdobywanej wiedzy. Naszym celem nie było dostarczenie programów gotowych do uruchomienia. Pełna implementacja niektórych z zaprezentowanych algorytmów wymaga pewnego wysiłku programistycznego. Zachęcamy cię do podjęcia go, ponieważ dopiero pełna, poprawna implementacja świadczy o dobrym zrozumieniu przerabianego materiału.

Większość przedstawionych tu algorytmów i struktur danych uważa się już dziś za klasyczne. Można je znaleźć (rozproszone) w licznych książkach poświęconych algorytmom (niestety w większości w języku angielskim). Czytelnikowi zainteresowanemu innym spojrzeniem na omawianą tematykę oraz poszerzaniem wiedzy dotyczącej problemów poruszanych w tym opracowaniu polecamy podane niżej pozycje.

A. V. Aho, J. E. Hopcroft, J. D. Ullman: Projektowanie i analiza algorytmów komputerowych

Jest to książka poświęcona algorytmom i strukturom danych z wielu różnych działów informatyki teoretycznej.

L. Banachowski, A. Kreczmar: Elementy analizy algorytmów

W książce tej przedstawiono podstawowe zasady analizy algorytmów, zilustrowane ciekawymi przykładami.

L. Banachowski, A. Kreczmar, W. Rytter: Analiza algorytmów i struktur danych

W książce tej omówiono złożone metody projektowania i analizowania algorytmów oraz struktur danych.

T. H. Cormen, C. E. Leiserson, R. L. Rivest: Wprowadzenie do algorytmów

W książce tej przedstawiono najważniejsze (od elementarnych do złożonych) algorytmy i struktury danych z wielu różnych dziedzin informatyki.

M. Crochemore, W. Rytter: Text algorithms

Jest to książka poświęcona algorytmom na tekstach.

A. Gibbons, W. Rytter: Efficient parallel algorithms

W książce tej omówiono algorytmy równoległe z wielu różnych działów informatyki teoretycznej.

J. Jaja: An introduction to parallel algorithms

Jest to wprowadzenie do problematyki algorytmów i obliczeń równoległych.

D. E. Knuth: The art of computer programming. Sorting and searching

W książce tej omówiono klasyczne metody sortowania i wyszukiwania.

W. Lipski: Kombinatoryka dla programistów

Jest to książka poświęcona podstawowym algorytmom grafowym.

K. Mehlhorn: Multi-dimensional searching and computational geometry

Tematem książki są problemy i algorytmy geometryczne.

F. P. Preparata, M. I. Shamos: Computational geometry (an introduction)

Jest to doskonałe wprowadzenie do problematyki geometrii obliczeniowej.

R. Sedgewick: Algorithms

W książce tej bardzo przystępnie omówiono różne algorytmy i struktury danych.

Na przedstawionej tu liście nie ma oczywiście wszystkich pozycji poświęconych algorytmom i strukturom danych. Wymieniliśmy tylko te, które wykorzystaliśmy do przygotowania notatek do wykładów, a następnie tej książki. Opis większości omawianych tu problemów, algorytmów i struktur danych można znaleźć w książkach z tej listy. W razie odstępstwa od powyższej zasady podajemy bezpośrednie źródło omawianego tematu.

Warszawa 1996 r.

1 Podstawowe zasady analizy algorytmów

W tym rozdziale przedstawiamy podstawowe pojęcia stosowane przy badaniu algorytmów i struktur danych. Przede wszystkim wyjaśniamy, na czym polega analiza algorytmu w dwóch głównych aspektach: poprawności semantycznej i złożoności obliczeniowej. Omawiamy elementarne struktury danych definiowane abstrakcyjnie (jako listy, zbiory, grafy, drzewa itd.), z możliwymi różnymi konkretnymi implementacjami (reprezentacjami). Na końcu rozdziału przedstawiamy podstawowe metody konstruowania efektywnych algorytmów (metoda „dziel i zwyciężaj”, programowanie dynamiczne, metoda zachłanna, metoda kolejnych transformacji).

Analiza algorytmów to dział informatyki zajmujący się szukaniem najlepszych algorytmów dla zadań komputerowych. Polega ona między innymi na znalezieniu odpowiedzi na następujące pytania.

1. Czy dany problem może być rozwiązany na komputerze w dostępnym czasie i pamięci?

2. Który ze znanych algorytmów należy zastosować w danych okolicznościach?

3. Czy istnieje lepszy algorytm od rozważanego? A może jest on optymalny?

4. Jak uzasadnić, że stosując dany algorytm, rozwiąże się zamierzone zadanie?

Dokonując analizy algorytmu, zwracamy uwagę na jego poprawność semantyczną, prostotę, czas działania, ilość wykorzystywanej pamięci, optymalność oraz okoliczności, w jakich należy go używać, a w jakich nie.

1.1.
Złożoność obliczeniowa

Złożoność obliczeniową algorytmu definiuje się jako ilość zasobów komputerowych potrzebnych do jego wykonania. Podstawowymi zasobami rozważanymi w analizie algorytmów są czas działania i ilość wykorzystywanej pamięci.

Zauważmy, że nie jest na ogół możliwe wyznaczenie złożoności obliczeniowej jako funkcji danych wejściowych (takich jak ciągi, tablice, drzewa czy grafy). Zwykle, co naturalne, z zestawem danych wejściowych jest związany jego rozmiar, rozumiany – mówiąc ogólnie – jako liczba pojedynczych danych wchodzących w jego skład.

W problemie sortowania na przykład za rozmiar przyjmuje się zazwyczaj liczbę elementów w ciągu wejściowym, w problemie przejścia drzewa binarnego – liczbę węzłów w drzewie, a w problemie wyznaczenia wartości wielomianu – stopień wielomianu. Rozmiar zestawu danych d będziemy oznaczać przez | d |.

Aby móc wyznaczać złożoność obliczeniową algorytmu, musimy się jeszcze umówić, w jakich jednostkach będziemy ją liczyć. Na złożoność obliczeniową składa się złożoność pamięciowa i złożoność czasowa. W wypadku złożoności pamięciowej za jednostkę przyjmuje się zwykle słowo pamięci maszyny. Sytuacja jest nieco bardziej skomplikowana w wypadku złożoności czasowej. Złożoność czasowa powinna być własnością samego tylko algorytmu jako metody rozwiązania problemu – niezależnie od komputera, języka programowania czy sposobu jego zakodowania. W tym celu wyróżnia się w algorytmie charakterystyczne dla niego operacje nazywane operacjami dominującymi – takie, że łączna ich liczba jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu.

Dla algorytmów sortowania na przykład za operację dominującą przyjmuje się zwykle porównanie dwóch elementów w ciągu wejściowym, a czasem też przestawienie elementów w ciągu; dla algorytmów przeglądania drzewa binarnego przyjmuje się przejście dowiązania między węzłami w drzewie, a dla algorytmów wyznaczania wartości wielomianu – operacje arytmetyczne +, –, * i /.

Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji dominującej.

Złożoność obliczeniową algorytmu traktuje się jako funkcję rozmiaru danych n. Wyróżnia się: złożoność pesymistyczną – definiowaną jako ilość zasobów komputerowych potrzebnych przy „najgorszych” danych wejściowych rozmiaru n, oraz złożoność oczekiwaną – definiowaną jako ilość zasobów komputerowych potrzebnych przy „typowych” danych wejściowych rozmiaru n.

Aby zdefiniować precyzyjnie pojęcia pesymistycznej i oczekiwanej złożoności czasowej, wprowadzimy następujące oznaczenia:

D_(n) – zbiór zestawów danych wejściowych rozmiaru n;

t(d) – liczba operacji dominujących dla zestawu danych wejściowych d;

X_(n) – zmienna losowa, której wartością jest t(d) dla d ∈ D_(n);

p_(nk) – rozkład prawdopodobieństwa zmiennej losowej X_(n), tzn. prawdopodobieństwo, że dla danych rozmiaru n algorytm wykona k operacji dominujących (k ≥ 0).

Rozkład prawdopodobieństwa zmiennej losowej X_(n) wyznacza się na podstawie informacji o zastosowaniach rozważanego algorytmu. Gdy na przykład zbiór D_(n) jest skończony, przyjmuje się często model probabilistyczny, w którym każdy zestaw danych rozmiaru n może się pojawić na wejściu do algorytmu z jednakowym prawdopodobieństwem.

Przez pesymistyczną złożoność czasową algorytmu rozumie się funkcję

W(n) = sup{t(d): d ∈ D_(n)},

gdzie sup oznacza kres górny zbioru.

Przez oczekiwaną złożoność czasową algorytmu rozumie się funkcję

tzn. wartość oczekiwaną ave(X_(n)) zmiennej losowej X_(n).

Aby stwierdzić, na ile funkcje W(n) i A(n) są reprezentatywne dla wszystkich danych wejściowych rozmiaru n, rozważa się miary wrażliwości algorytmu: miarę wrażliwości pesymistycznej, czyli Δ(n) = sup{t(d₁) – t(d₂): d₁, d₂∈ D_(n)}, oraz miarę wrażliwości oczekiwanej, czyli δ(n) = dev(X_(n)), gdzie dev(X_(n)) jest standardowym odchyleniem zmiennej losowej X_(n), tzn. i (var(X_(n)) jest wariancją zmiennej losowej X_(n)). Im większe są wartości funkcji Δ(n) i δ(n), tym algorytm jest bardziej wrażliwy na dane wejściowe i tym bardziej jego zachowanie w przypadku rzeczywistych danych może odbiegać od zachowania opisanego funkcjami W(n) i A(n).

◻ PRZYKŁAD: Przeszukiwanie sekwencyjne ciągu.

Dane wejściowe: L, N, a, gdzie N jest liczbą naturalną N ≥ 0, a jest poszukiwanym elementem, L jest tablicą, w której na miejscach od 1 do N znajdują się elementy ciągu.

Wynik: Zmienna logiczna p taka, że p = true ≡ a znajduje się w L.

Algorytm:

begin

j := 1;

L := a;

while L ≠ a do j := j + 1;

p := j ≤ N

end;

Rozmiar danych wejściowych: n = N

Operacja dominująca: porównanie: L ≠ a

Pesymistyczna złożoność czasowa: W(n) = n + 1

Pesymistyczna wrażliwość czasowa: Δ(n) = n

A jaka jest oczekiwana złożoność czasowa? Załóżmy, że prawdopodobieństwo znalezienia a na każdym z n możliwych miejsc jest takie samo i wiadomo, że a jest w L, tzn. że

Wówczas

Oczekiwana wrażliwość czasowa:

czyli

δ(n) ≅ 0,29n

Zauważmy, że zarówno funkcje wrażliwości powyższego algorytmu, jak i funkcje jego złożoności są liniowe; wynika stąd duża wrażliwość liczby operacji dominujących na dane wejściowe.

Faktyczna złożoność czasowa algorytmu (czas działania) w chwili jego użycia jako programu różni się od wyliczonej teoretycznie współczynnikiem proporcjonalności, który zależy od konkretnej realizacji tego algorytmu. Istotną zatem częścią informacji, która jest zawarta w funkcjach złożoności W(n) i A(n), jest ich rząd wielkości, czyli ich zachowanie asymptotyczne, gdy n dąży do nieskończoności. Zwykle staramy się podać jak najprostszą funkcję charakteryzującą rząd wielkości W(n) i A(n), na przykład n, n log n, n², n³.

Używamy w tym celu następujących oznaczeń dla rzędów wielkości funkcji. Niech f, g, h: N → R₊∪ {0}, gdzie N i R₊ oznaczają zbiory liczb – odpowiednio – naturalnych i rzeczywistych dodatnich.

Mówimy, że f jest co najwyżej rzędu g, co zapisujemy jako f (n) = O(g(n)), jeśli istnieją stała rzeczywista c > 0 i stała naturalna n_(O) takie, że nierówność f(n) ≤ cg(n) zachodzi dla każdego n ≥ n_(O). Oto przykład: n² + 2n = O(n²), bo n² + 2n ≤ 3n² dla każdego naturalnego n.

Mówimy, że f jest co najmniej rzędu g, co zapisujemy jako f(n) = Ω(g(n)), jeśli g(n) = O (f (n)).

Mówimy, że f jest dokładnie rzędu g, co zapisujemy jako f(n) = Θ(n), jeśli zarówno f(n) = O(g(n)), jak i f(n) = Ω(g(n)). Poprawny jest też termin f jest asymptotycznie równoważne g i oznaczenie f(n) ≅ g(n). Oto przykład: n² + 2n ≅ n², bo zarówno n² + 2n ≤ 3n², jak i n² + 2n ≥ n² dla każdego n ≥ 0.

Będziemy także używać oznaczenia f(n) = g(n) + O(h(n)), gdy f(n) – g(n) = O(h(n)), na przykład (1/2) n² + 5 n + 1 = (1/2) n² + O(n). Zauważmy, że w ten sposób zachowujemy współczynnik proporcjonalności przy najbardziej znaczącym składniku sumy i pomijamy współczynniki przy mniej znaczących składnikach sumy.

Rzędy wielkości dwóch funkcji f(n) i g(n) mogą być porównane przez obliczenie granicy

Jeśli E = +∞ , to g(n) = O(f(n)), ale nie f(n) = O(g(n)).

Jeśli E = c > 0, to f(n) ≅ g(n).

Jeśli E = 0, to f(n) = O(g(n)), ale nie g(n) = O(f(n)).

Stosując na przykład regułę de L‘Hospitala, otrzymujemy

czyli n log n = O(n²), ale nie n² = O(n log n).

Większość rozważanych algorytmów ma złożoność czasową proporcjonalną do jednej z podanych tu funkcji.

log n – złożoność logarytmiczna

Czas działania logarytmiczny występuje na przykład dla algorytmów typu: zadanie rozmiaru n zostaje sprowadzone do zadania rozmiaru n/2 + pewna stała liczba działań, na przykład poszukiwanie binarne w ciągu uporządkowanym a₁≤ a₂≤ ... ≤ a_(n).

Aby stwierdzić, czy x znajduje się w tym ciągu, porównujemy x najpierw z . Jeśli to szukamy dalej x w ciągu Jeśli natomiast to szukamy x w ciągu (następny podciąg jest zawsze co najmniej o połowę krótszy).

n – złożoność liniowa

Czas działania liniowy występuje na przykład dla algorytmów, w których jest wykonywana pewna stała liczba działań dla każdego z n elementów danych wejściowych. Przykładem takiego algorytmu jest algorytm Hornera wyznaczania wartości wielomianu.

n log n – złożoność n log n (liniowo-logarytmiczna)

Czas działania n log n występuje na przykład dla algorytmów typu: zadanie rozmiaru n zostaje sprowadzone do dwóch podzadań rozmiaru n/2 plus pewna liczba działań, liniowa względem rozmiaru n, potrzebnych do wykonania najpierw rozbicia, a następnie scalenia rozwiązań rozmiaru n/2 w rozwiązanie rozmiaru n. W ten sposób działa mergesort – algorytm sortowania przez scalanie. Aby uporządkować ciąg a₁, a₂, ..., a_(n), sortujemy najpierw niezależnie podciągi:

a następnie scalamy posortowane podciągi w jeden uporządkowany ciąg.

n² – złożoność kwadratowa

Czas działania kwadratowy występuje na przykład dla algorytmów, w których jest wykonywana pewna stała liczba działań dla każdej pary elementów danych wejściowych (podwójna instrukcja iteracyjna).

n³, n⁴, … – następne złożoności wielomianowe

n ^(log) ^(n) = 2 ^(log) ^(2n) – złożoność podwykładnicza

2^(n) – złożoność wykładnicza 2^(n)

Czas działania 2^(n) ma na przykład algorytm, w którym jest wykonywana stała liczba działań dla każdego podzbioru danych wejściowych.

n! – złożoność wykładnicza n!

Czas działania n! ma na przykład algorytm, w którym jest wykonywana stała liczba działań dla każdej permutacji danych wejściowych.

Zauważmy, że algorytm o złożoności wykładniczej może być zrealizowany jedynie dla małych rozmiarów danych. Istnieje próg, od którego funkcja wykładnicza zaczyna rosnąć tak szybko, że realizacja algorytmu na komputerze staje się niemożliwa. Załóżmy na przykład, że dla danych rozmiaru n jest wykonywanych 2^(n) operacji jednostkowych i że każda operacja jednostkowa zajmuje odpowiednio 10^(–6) i 10^(–9) sekund na dwóch różnych komputerach. Czas działania potrzebny do realizacji algorytmu jest przedstawiony w tabeli 1.1. Sytuacja niewiele się zmieniła, nawet przy współczesnych, o wiele szybszych komputerach.

Tabela 1.1. Porównanie czasów realizacji algorytmu wykładniczego na dwóch komputerach

+----------------+-------------+-------------+-----------------+-----------------+
| Rozmiar n | 20 | 50 | 100 | 200 |
+----------------+-------------+-------------+-----------------+-----------------+
| Czas działania | 1,04 s | 35,7 lat | 4 × 10¹⁴ wieków | 5 × 10⁴⁴ wieków |
| | | | | |
| (2^(n)/10⁶) | | | | |
+----------------+-------------+-------------+-----------------+-----------------+
| Czas działania | 0,001 s | 13 dni | 4 × 10¹¹ wieków | 5 × 10⁴¹ wieków |
| | | | | |
| (2^(n)/10⁹) | | | | |
+----------------+-------------+-------------+-----------------+-----------------+

Widać, że nawet 1000-krotne przyspieszenie szybkości działania komputera niewiele pomaga algorytmowi wykładniczemu. Nierealizowalność uważa się za wewnętrzną cechę algorytmu o złożoności wykładniczej. Aby jednak mieć pełny obraz sytuacji, powinniśmy jeszcze rozważyć wrażliwość algorytmu na dane wejściowe. Może się zdarzyć, że dla danego algorytmu W(n) = 2^(n) + O(1), ale także Δ(n) = 2^(n) + O(1). Wówczas nie możemy twierdzić, że algorytm jest nierealizowalny dla reprezentatywnych danych. Dane wejściowe, dla których czas działania jest wykładniczy, mogą się nigdy nie pojawić w rzeczywistych okolicznościach! Właśnie taka sytuacja zachodzi dla metody simplex programowania liniowego. Choć metoda ta ma złożoność wykładniczą dla „najgorszych” danych, dla pojawiających się w praktyce danych wejściowych działa w czasie wielomianowym, a nawet liniowym. Co więcej, w wypadku takich danych przewyższa metodę elipsoidalną, której pesymistyczna złożoność czasowa jest wielomianowa!

Przy korzystaniu z wyników analizy złożoności algorytmu należy zatem brać pod uwagę następujące uwarunkowania:

• algorytm i jego realizacja przeznaczona do wykonania są zwykle wyrażone w dwóch całkowicie różnych językach;

• wrażliwość algorytmu na dane wejściowe może spowodować, że faktyczne zachowanie się algorytmu na używanych danych będzie odbiegać od zachowania opisanego funkcjami złożoności W(n) i A(n);

• może być trudno przewidzieć rzeczywisty rozkład prawdopodobieństwa zmiennej losowej X_(n);

• dla niektórych algorytmów nie są znane matematyczne oszacowania wielkości W(n) i A(n); szczególnie wyznaczenie A(n) dla rzeczywistego rozkładu prawdopodobieństwa może stanowić bardzo trudny problem matematyczny;

• czasami działanie dwóch algorytmów trudno jest jednoznacznie porównać; jeden działa lepiej dla pewnej klasy zestawów danych, a drugi dla innych.

Ważną cechą algorytmu jest jego prostota, z której zwykle wynika mniejszy współczynnik proporcjonalności przy złożoności obliczeniowej oraz łatwość realizacji (zaprogramowania). Szczególnie więc w dwóch przypadkach:

• program, w którym jest stosowany nasz algorytm, ma być wykonany raz lub tylko kilka razy;

• algorytm ma być stosowany tylko dla małych rozmiarów danych;

należy wybierać algorytm raczej pod kątem jego prostoty niż małej złożoności obliczeniowej (oczywiście najlepiej używać zawsze algorytmów zarówno prostych, jak i szybkich w sensie asymptotycznym).

1.2.
Równania rekurencyjne

Wyznaczenie złożoności algorytmu sprowadza się często do rozwiązania równania rekurencyjnego. Stosowane są zwykle dwie metody: (1) rozwinięcie równania do sumy i (2) znalezienie funkcji tworzącej.

Metodą 2 zajmiemy się w następnym podrozdziale. Teraz pokażemy zastosowanie metody 1 do rozwiązania trzech często pojawiających się równań rekurencyjnych (c oznacza stałą naturalną dodatnią).

(1)

(Równanie to otrzymujemy jako równanie złożoności wtedy, kiedy problem rozmiaru n sprowadza się do podproblemu rozmiaru połowę mniejszego).

Rozwiązujemy to równanie dla n = 2^(k) (tj. potęgi dwójki) i stąd możemy już wnioskować (zob. zad. 1.4), że rząd wielkości rozwiązania oryginalnego równania jest taki sam jak równania dla potęg dwójki.

Podstawmy więc n = 2^(k). Wtedy

T(2^(k)) = T(2^(k–\ 1)) + c = T(2^(k–\ 2)) + c + c = T(2⁰) + kc = kc = c log n

Stąd wynika, że

T(n) = Θ(log n)

(2)

(Równanie to otrzymujemy jako równanie złożoności wtedy, kiedy problem rozmiaru n sprowadza się do dwóch podproblemów rozmiaru n/2 + stała liczba działań). Podstawmy więc n = 2^(k). Wtedy

Stąd, jak poprzednio, wnioskujemy, że

T(n) = Θ(n)

(3)

(Równanie to otrzymamy jako równanie złożoności wtedy, kiedy problem rozmiaru n sprowadza się do dwóch podproblemów rozmiaru n/2 + liniowa liczba działań). Podstawmy n = 2^(k). Wtedy

T(2^(k)) = 2T(2^(k–\ 1)) + c2^(k) = 2(2T(2^(k–\ 2)) + c2^(k–\ 1)) + c2^(k) =

= 2² T(2^(k–\ 2)) + c2^(k) + c2^(k) = 2^(k) T(2⁰) + kc2^(k) = 0 + cn log n

Mamy zatem

T(n) = Θ(n log n)

1.3.
Funkcje tworzące

Czasami trudno wyznaczyć rozwiązanie równania T(n) bezpośrednio z równania rekurencyjnego (może nie istnieć zwięzły wzór). Można wówczas spróbować zastosować metodę funkcji tworzących, która polega na znalezieniu funkcji

nazywanej funkcją tworzącą T(n), i na jej podstawie wnioskować o własnościach samej funkcji T(n).

Metodę tę stosuje się często w analizie probabilistycznej algorytmów (do wyznaczenia wartości oczekiwanej i wariancji zmiennej losowej X_(n)). Rozważmy funkcję tworzącą rozkładu prawdopodobieństwa p_(nk) zmiennej losowej X_(n) (z równań rekurencyjnych na p_(nk) trudno jest często wyznaczyć rozwiązanie):

Zauważmy, że wówczas

Wartość oczekiwaną i wariancję zmiennej losowej X_(n) można wyrazić za pomocą wartości pochodnych funkcji P_(n)(z) dla z = 1 w następujący sposób:

ponieważ

i

Stąd a zatem

Można więc wyznaczyć wielkości ave(X_(n)) i var(X_(n)) (a co za tym idzie również złożoność oczekiwaną i oczekiwaną wrażliwość algorytmu), nie znając explicité rozkładu p_(nk), a tylko jego funkcję tworzącą.

1.4.
Poprawność semantyczna

Poprawność semantyczna oznacza, że program wykonuje postawione przed nim zadanie. Stosowaną metodą dowodu jest indukcja matematyczna względem liczby powtórzeń instrukcji iteracyjnej bądź poziomu zagnieżdżenia realizacji procedury rekurencyjnej. Rozważmy na przykład algorytm potęgowania binarnego:

{n ≥ 0}

z := x; y := 1; m := n;

while m ≠ 0 do {γ:x^(n) = y*z^(m) ∧ m ≥ 0}

begin

if odd(m) then y := y*z;

m := m div 2;

z := z*z

end;

{y = x^(n)}

Warunek γ, nazywany niezmiennikiem instrukcji iteracyjnej, opisuje wartości zmiennych w trakcie realizacji programu. Zamieszczony warunek γ jest spełniony na początku, gdy rozpoczyna się realizacja instrukcji iteracyjnej, i każda iteracja zachowuje go. Zachodzi on zatem, gdy kończy się realizacja instrukcji iteracyjnej, z czego łatwo wyprowadzić warunek końcowy y = x^(n). Niezmiennik jest zwykle rozszerzeniem warunku końcowego, jak to zwykle bywa przy dowodach indukcyjnych. Chociaż przedstawiony dowód dowodzi warunku {y = x^(n)}, to jednak nie tłumaczy działania algorytmu. Aby zrozumieć, jak działa algorytm, przypatrzmy się postaci binarnej liczby m wewnątrz pętli.

{n = (a_(l)a_(l-1)...a₀)₂, ai ∈ {0, 1}, a_(l) = 1}

z := x; y := 1; m := n; k := 0;

while m > 0 do

begin

{γ : m = (a₁...a_(k))₂∧ z = x^(2k) ∧ y = x^((ak-1...a0)2) ∧ l ≥ k ∧ a_(l) = 1}

if odd(m) then y := y*z;

m := m div 2; z := z*z;

k := k + 1

end;

{y = x^(n)}

Zazwyczaj wymaga się od dowodów poprawności, aby na ich podstawie można było zrozumieć, jak faktycznie działa algorytm i dlaczego jest poprawny.

Aby dowód poprawności był kompletny, musimy jeszcze dodatkowo udowodnić dwie własności:

• wykonalność operacji częściowych, jak dzielenie, przechodzenie po dowiązaniu w drzewie lub liście, określenie zmiennej indeksowanej itp.;

• skończoność działania każdej instrukcji iteracyjnej i każdego wywołania procedury rekurencyjnej.

W przypadku algorytmu potęgowania binarnego jedyna częściowa operacja div jest zawsze wykonalna (gdyż dzielimy przez 2) oraz obliczenie instrukcji iteracyjnej jest kończone na mocy następującej własności liczb naturalnych: dla każdej liczby naturalnej n, wykonując wielokrotnie dzielenie całkowite n przez 2, po skończonej liczbie kroków otrzymamy 0. Co więcej, liczba wykonań instrukcji iteracyjnej jest równa liczbie dzieleń całkowitych przez 2, czyli długości binarnej n. Dla n > 0 mamy zatem

(rozmiarem danych jest n, a operacją dominującą dzielenie całkowite przez 2). Widzimy, że w tym przypadku dowodzenie skończoności działania instrukcji iteracyjnej jest powiązane ze znajdowaniem pesymistycznej złożoności czasowej.

Jako przykład algorytmu rekurencyjnego rozważmy algorytm Euklidesa znajdowania największego wspólnego dzielnika dwóch dodatnich liczb naturalnych.

function NWD(x, y : integer) : integer;

var r : integer;

begin {α: x > 0 ∧ y > 0}

r := x mod y;

if r = 0 then NWD := y else NWD := NWD(y, r)

{β:NWD = (x, y)}

end;

Przez (x, y) oznaczyliśmy największy wspólny dzielnik dodatnich liczb naturalnych x i y. Poprawność funkcji NWD względem podanych warunków pokazujemy, dowodząc, że dla każdych dodatnich wartości naturalnych x i y obliczenie wywołania funkcji NWD(x, y) kończy się z wartością NWD = (x, y). Stosujemy indukcję względem wartości y. Zakładając poprawność dla wszystkich z, 0 < z < y, otrzymujemy, że gdy x mod y = 0, wówcza (x, y) = y, natomiast w przeciwnym przypadku możemy zastosować założenie indukcyjne dla pary (y, x mod y) i wewnętrznego wywołania rekurencyjnego. Wtedy (x, y) = (y, x mod y).

1.5.
Podstawowe struktury danych

Poniżej rozważamy podstawowe struktury danych: listę, graf, zbiór i drzewo, wprowadzając potrzebne w dalszej części książki oznaczenia i omawiając podstawowe metody implementacji tych struktur. Będziemy zakładać, że elementy wchodzące w skład rozważanych struktur danych pochodzą z pewnego niepustego uniwersum U. Jak wiadomo z zasad programowania strukturalnego, zagadnienia dotyczące budowy samej struktury danych i jej użycia w algorytmie wygodnie jest rozważać oddzielnie.

1.5.1.
Lista

Lista to skończony ciąg elementów: q = . Skrajne elementy listy x₁ i x_(n) nazywają się końcami listy (odpowiednio – lewym i prawym), a wielkość | q | = n – długością (lub rozmiarem) listy. Szczególnym przypadkiem listy jest lista pusta: q = .

Weźmy dwie listy: q = i r = , i niech 0 ≤ i ≤ j ≤ n:

Podstawowymi abstrakcyjnymi operacjami na listach są:

• dostęp do elementu listy – q = x_(i);

• podlista – q = ;

• złożenie – q&r = .

Za pomocą tych trzech podstawowych operacji można definiować inne operacje na listach, na przykład wstawianie elementu x za element x_(i) na liście q: q & & q .

Listy używa się zwykle w specjalny sposób, ograniczając się do zmian jej końców:

(a) front(q) = q (pobieranie lewego końca listy);

(b) push(q, x) = &q (wstawienie elementu x na lewy koniec listy);

(c) pop(q) = q (usunięcie bieżącego lewego końca listy);

(d) rear(q) = q (pobieranie prawego końca listy);

(e) inject(q, x) = q& (wstawienie elementu x na prawy koniec listy);

(f) eject(q) = q (usunięcie bieżącego prawego końca listy).

Listę, na której można wykonać wszystkich sześć operacji, nazywa się kolejką podwójną. W szczególnych przypadkach, tzn. kiedy uwzględnia się tylko operacje front, push i pop, nazywa się ją stosem, a kiedy uwzględnia się tylko operacje front, pop i inject – kolejką. (Operacje na abstrakcyjnej strukturze danych mogą być realizowane za pomocą funkcji albo procedur).

Dwie podstawowe implementacje (reprezentacje) listy q = to:

• tablicowa – q = x_(i), gdzie 1 ≤ i ≤ n,

• dowiązaniowa – różne warianty są przedstawione na rysunku 1.1.

W implementacjach pojedynczej liniowej i podwójnej liniowej dowiązanie prowadzące do listy wskazuje na pierwszy element na liście, a w implementacji pojedynczej cyklicznej i podwójnej cyklicznęj na ostatni. Aby mieć gwarancję, że struktura dowiązaniowa nigdy nie będzie pusta, dodaje się na początku listy element pusty, nazywany głową lub wartownikiem listy.

Rys. 1.1. Różne warianty implementacji dowiązaniowej list

Następujące operacje na listach mają stałą złożoność czasową:

• w implementacji pojedynczej liniowej: operacje stosu, wstawianie jednego elementu za drugi, usuwanie następnego elementu;

• w implementacji pojedynczej cyklicznej: te operacje co wyżej plus złożenie oraz operacje rear i inject;

• w implementacji podwójnej cyklicznej: te operacje co wyżej plus eject, wstawianie jednego elementu przed drugim, usuwanie danego elementu, odwracanie listy.

Każda zatem operacja dotycząca kolejki podwójnej ma pesymistyczną złożoność czasową O(1) w implementacji podwójnej cyklicznej. Wadą tej implementacji jest użycie O(n) komórek pomocniczej pamięci na pamiętanie dowiązań (n jest rozmiarem listy).

Jeśli jest znana maksymalna długość m kolejki podwójnej, to bardziej oszczędna pamięciowo jest implementacja listy za pomocą tablicy cyklicznej Q, w której następnikiem pozycji 0 ≤ i ≤ m – 1 jest pozycja (i + 1) mod m. Wówczas jeśli q = , to Q = x_(i) dla 1 ≤ i ≤ n i pewnej pozycji 0 ≤ k ≤ m – 1. Przykładowo operacja pop(q) ma implementację:

pop(k, n) :: if n = 0

then error

else

begin

k := (k + 1)mod m;

n := n – 1

end;

a operacja push(q, x):

push(k, n, x) :: if n = m

then error

else

begin

Q := x;

k := (k – 1)mod m;

n := n + 1

end;

1.5.2.
Zbiór

W przeciwieństwie do elementów listy elementy w zbiorze S = {x₁, x₂, ..., x_(n)} nie są podane w żadnym ustalonym porządku. (Zawsze będziemy zakładać, że rozważany zbiór jest skończony). Liczbę n elementów w zbiorze S oznaczamy przez |S| i nazywamy rozmiarem zbioru S. Podstawowymi operacjami na zbiorach są:

(a) insert(x, S):: S := S ∪ {x} (wstawienie elementu x do zbioru S);

(b) delete(x, S):: S := S – {x} (usunięcie elementu x ze zbioru S);

(c) member(x, S):: wynikiem jest wartość

(sprawdzenie, czy x jest elementem zbioru S);

(d) min(S):: zwrócenie najmniejszego elementu w zbiorze S z uwzględnieniem

pewnego ustalonego liniowego porządku ≤;

(e) deletemin(S):: S := S – {min(S)};

(f) union(S₁, S₂):: obliczenie S₁∪ S₂ (przy założeniu, że zbiory S₁ i S₂ są rozłączne).

Oto podstawowe implementacje zbioru S = {x₁, x₂, ..., x_(n)}.

• Wektor charakterystyczny

Przy założeniu, że uniwersum U może służyć jako zbiór indeksów dla tablicy C, mamy

Operacje insert, delete i member mają pesymistyczną złożoność czasową O(1). Złożoność pamięciowa jest proporcjonalna do rozmiaru zbioru indeksów tablicy C (czyli faktycznie do rozmiaru uniwersum U).

• Implementacje listowe

Oczywiście ustawiając elementy zbioru S w pewnym porządku, otrzymujemy listę. Wszystkie implementacje listy mogą być użyte do reprezentowania zbioru. Przy rozważanych wcześniej implementacjach listy pesymistyczna złożoność czasowa podstawowych operacji na zbiorach jest proporcjonalna do rozmiaru zbiorów.