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:
Dn - zbiór zestawów danych wejściowych rozmiaru n;
t(d) - liczba operacji dominujących dla zestawu danych wejściowych d;
Xn - zmienna losowa, której wartością jest t(d) dla d ? Dn;
pnk - rozkład prawdopodobieństwa zmiennej losowej Xn, tzn. prawdopodobieństwo, że dla danych rozmiaru n algorytm wykona k operacji dominujących (k ? 0).
Rozkład prawdopodobieństwa zmiennej losowej Xn wyznacza się na podstawie informacji o zastosowaniach rozważanego algorytmu. Gdy na przykład zbiór Dn 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 ? Dn},
gdzie sup oznacza kres górny zbioru.
Przez oczekiwaną złożoność czasową algorytmu rozumie się funkcję
tzn. wartość oczekiwaną ave(Xn) zmiennej losowej Xn.
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(d1) - t(d2): d1, d2? Dn}, oraz miarę wrażliwości oczekiwanej, czyli ?(n) = dev(Xn), gdzie dev(Xn) jest standardowym odchyleniem zmiennej losowej Xn, tzn. i (var(Xn) jest wariancją zmiennej losowej Xn). 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[1 .. N + 1] 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[1 .. N].
Algorytm:
begin
j := 1;
L[N + 1] := a;
while L[j] ? a do j := j + 1;
p := j ? N
end;
Rozmiar danych wejściowych: n = N
Operacja dominująca: porównanie: L[j] ? 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[1 .. N], 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, n2, n3.
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 nO takie, że nierówność f(n) ? cg(n) zachodzi dla każdego n ? nO. Oto przykład: n2 + 2n = O(n2), bo n2 + 2n ? 3n2 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: n2 + 2n ? n2, bo zarówno n2 + 2n ? 3n2, jak i n2 + 2n ? n2 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) n2 + 5 n + 1 = (1/2) n2 + 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(n2), ale nie n2 = 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 a1? a2? ... ? an.
Aby stwierdzić, czy x znajduje się w tym ciągu, porównujemy x najpierw z [1]. 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 a1, a2, ..., an, sortujemy najpierw niezależnie podciągi:
a następnie scalamy posortowane podciągi w jeden uporządkowany ciąg.
n2 - 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).
n3, n4, ... - następne złożoności wielomianowe
n log n = 2 log 2n - złożoność podwykładnicza
2n - złożoność wykładnicza 2n
Czas działania 2n 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 2n 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
(2n/106)
1,04 s
35,7 lat
4 × 1014 wieków
5 × 1044 wieków
Czas działania
(2n/109)
0,001 s
13 dni
4 × 1011 wieków
5 × 1041 wieków
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) = 2n + O(1), ale także ?(n) = 2n + 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 Xn;
- 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 = 2k (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 = 2k. Wtedy
T(2k) = T(2k- 1) + c = T(2k- 2) + c + c = T(20) + 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 = 2k. 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 = 2k. Wtedy
T(2k) = 2T(2k- 1) + c2k = 2(2T(2k- 2) + c2k- 1) + c2k =
= 22 T(2k- 2) + c2k + c2k = 2k T(20) + kc2k = 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 Xn). Rozważmy funkcję tworzącą rozkładu prawdopodobieństwa pnk zmiennej losowej Xn (z równań rekurencyjnych na pnk trudno jest często wyznaczyć rozwiązanie):
Zauważmy, że wówczas
Wartość oczekiwaną i wariancję zmiennej losowej Xn można wyrazić za pomocą wartości pochodnych funkcji Pn(z) dla z = 1 w następujący sposób:
ponieważ
i
Stąd a zatem
Można więc wyznaczyć wielkości ave(Xn) i var(Xn) (a co za tym idzie również złożoność oczekiwaną i oczekiwaną wrażliwość algorytmu), nie znając explicité rozkładu pnk, 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 {?:xn = y*zm ? m ? 0}
begin
if odd(m) then y := y*z;
m := m div 2;
z := z*z
end;
{y = xn}
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 = xn. Niezmiennik jest zwykle rozszerzeniem warunku końcowego, jak to zwykle bywa przy dowodach indukcyjnych. Chociaż przedstawiony dowód dowodzi warunku {y = xn}, 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 = (alal-1...a0)2, ai ? {0, 1}, al = 1}
z := x; y := 1; m := n; k := 0;
while m > 0 do
begin
{? : m = (a1...ak)2? z = x2k ? y = x(ak-1...a0)2 ? l ? k ? al = 1}
if odd(m) then y := y*z;
m := m div 2; z := z*z;
k := k + 1
end;
{y = xn}
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[2] to skończony ciąg elementów: q = [x1, x2, ..., xn]. Skrajne elementy listy x1 i xn 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 = [x1, x2, ..., xn] i r = [y1, y2, ..., ym], i niech 0 ? i ? j ? n:
Podstawowymi abstrakcyjnymi operacjami na listach są:
- dostęp do elementu listy - q[i] = xi;
- podlista - q[i .. j] = [xi, xi+ 1, ..., xj];
- złożenie - q&r = [x1, ..., xn, y1, ..., ym].
Za pomocą tych trzech podstawowych operacji można definiować inne operacje na listach, na przykład wstawianie elementu x za element xi na liście q: q [1 .. i] & [x] & q [i + 1 .. | q |].
Listy używa się zwykle w specjalny sposób, ograniczając się do zmian jej końców:
(a) front(q) = q[1] (pobieranie lewego końca listy);
(b) push(q, x) = [x]&q (wstawienie elementu x na lewy koniec listy);
(c) pop(q) = q[2 .. | q |] (usunięcie bieżącego lewego końca listy);
(d) rear(q) = q[| q |] (pobieranie prawego końca listy);
(e) inject(q, x) = q&[x] (wstawienie elementu x na prawy koniec listy);
(f) eject(q) = q[1 .. | q | - 1] (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 = [x1, x2, ..., xn] to:
- tablicowa - q[i] = xi, 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[0 .. m - 1], w której następnikiem pozycji 0 ? i ? m - 1 jest pozycja (i + 1) mod m. Wówczas jeśli q = [x1, x2, ..., xn], to Q[(k + i) mod m] = xi 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[3]
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[k] := 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 = {x1, x2, ..., xn} 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(S1, S2):: obliczenie S1? S2 (przy założeniu, że zbiory S1 i S2 są rozłączne).
Oto podstawowe implementacje zbioru S = {x1, x2, ..., xn}.
- 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.
