Wykład Algorytmy i struktury danych jest poświęcony przede wszystkim koncepcyjnym i strukturalnym metodom efektywnego rozwiązywania problemów na komputerze. Podstawowym elementem przy rozwiązywaniu zadanego problemu jest dobór algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego poprawność i złożoność (czasowa i pamięciowa).
W przypadku złożoności czasowej, z reguły wyróżnimy pewną operację dominującą, a czas będziemy traktować jako liczbę wykonanych operacji dominujących. W ten sposób nasza analiza będzie zależna jedynie od algorytmu, a nie od implementacji i sprzętu. W przypadku sortowania, operacją dominującą jest przeważnie porównanie dwóch elementów, a w przypadku przeglądania drzewa - jedno przejście w drzewie między wierzchołkami. W przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch symboli. Zazwyczaj określamy pewien parametr \( n \), będący rozmiarem problemu wejściowego i określamy złożoność jako funkcję \( T(n) \), której argumentem jest rozmiar problemu. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się wykonać w jednym kroku. Przez "małe" rozumiemy liczby mające \( O(\log n) \) bitów.
Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego przypadku lub złożoności średniej. Złożoność najgorszego przypadku nazywamy złożonością pesymistyczną - jest to maksymalna złożoność dla danych tego samego rozmiaru \( n \). W praktyce ważniejsza może się okazać złożoność średnia lub oczekiwana. W tym przypadku \( T(n) \) jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów rozmiaru \( n \). Tego typu złożoność zależy istotnie od tego, jaka się pod tym kryje przestrzeń probabilistyczna danych wejściowych. Z reguły zakładamy, że wszystkie dane wejściowe tego samego rozmiaru mogą się pojawić z tym samym prawdopodobieństwem. Jednakże jest to często mało realistyczne założenie. Przestrzeń probabilistyczna danych wejściowych może być bardzo skomplikowana. Prowadzić to może do bardzo trudnych (i wykraczających poza ten kurs) analiz.
Rozważmy następujący przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę w n-elementowej tablicy zerojedynkowej i nasz algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy. Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to wykonamy \( n \) sprawdzeń. Jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi \( T(n)=n \). Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem, to łatwo policzyć, że złożoność średnia jest ograniczona przez stałą.
Do wyrażania złożoności stosujemy opis asymptotycznego wzrostu funkcji: \( f(n)\ =\ O(g(n)) \) oznacza, że \( f(n) \le c\cdot g(n) \) dla pewnej stałej \( c \). Gdy \( g(n)=n \), to mówimy, że \( f(n) \) jest liniowa, oraz dla \( g(n)=n^2 \) mówimy, że złożoność \( f(n) \) jest kwadratowa. Jeśli \( g(n) \) jest wielomianem, to wtedy mówimy o złożoności wielomianowej.
Będziemy używać dodatkowych notacji:
\( f(n)=\Theta(g(n)),\ f(n)=\Omega(n) \). Były one wprowadzone na wykładach z matematyki dyskretnej.
PRZYKŁAD
\( \frac{1}{100}\cdot n^2- 2n = \Theta(n^2 ), n^5+2^n = \Theta(2^n), n!=\Omega(10^n) \),
Konwencje językowe. Jaki jest najlepszy język do opisu algorytmu? Jest to przykład problemu nierozstrzygalnego. Niewątpliwie język ojczysty jest najlepszym językiem potocznym, a ulubiony język programowania jest najlepszym językiem do implementacji algorytmu. Język, którym będziemy opisywać algorytmy, jest gdzieś pomiędzy tymi językami - język potoczny nie wystarcza, a konkretny język programowania może spowodować, że "prosty" algorytm się zrobi nieczytelny. Będziemy używać, o ile się da, nieformalnych konstrukcji programistycznych, a w przypadkach bardzo prostych będziemy się starali pisać algorytm w języku Pascalopodobnym.