Struktury danych/Złożoność obliczeniowa

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Złożoność obliczeniowa

Wybierając konkretny algorytm do rozwiązania problemu, programista powinien wiedzieć, czego może się po nim spodziewać oraz jak jego zastosowanie wpłynie na działanie aplikacji. Często trzeba wybierać spośród kilku możliwych algorytmów i wtedy konieczne jest wprowadzenie jakiegoś kryterium pozwalającego precyzyjnie określić, który z nich jest "najlepszy". Operując na dużych zbiorach danych, najbardziej korzystne jest przyjęcie definicji, w myśl której najlepszy algorytm najefektywniej wykorzystuje dostępne zasoby komputera (pamięć oraz procesor) do jak najszybszego rozwiązania problemu i zaprezentowania wyników. W ten sposób odpowiedzieliśmy sobie na pytanie, czym jest złożoność obliczeniowa

Pomiar szybkości algorytmu

Czas wykonania danego algorytmu zależy od wielu czynników:

1. Jakości kodu napisanego przez programistę i wygenerowanego przez kompilator
2. Szybkości sprzętu, na którym jest on wykonywany
3. Rozmiaru danych wejściowych
4. Użytego algorytmu

Jakość kodu oraz sprzętu to czynniki czysto subiektywne, które czasem ciężko jest nawet dokładnie określić. Jeśli przyjmiemy, że wszystkie nasze algorytmy badamy na tym samym komputerze i kompilujemy tym samym kompilatorem, oba te czynniki będą mogły zostać wyrażone przez pewną stałą, którą oznaczymy sobie literą c. Idźmy dalej - skoro szybkość algorytmu zależy od rozmiaru danych wejściowych, od razu powinno nasunąć to nam podejrzenia, że szybkość algorytmu możemy wyrazić za pomocą pewnej funkcji matematycznej, której argumentem jest rozmiar danych wejściowych n. Na przykład w przypadku sortowania, n może określać liczbę elementów, które chcemy posortować. Ostateczna postać funkcji zależy od użytego algorytmu.

Przyjęło się, że czas wykonywania algorytmu oznaczany jest przez T(n). Jednostka, w jakiej podawany jest wynik, jest nieważna. Można przyjąć, że jest to liczba instrukcji, jakie musi wykonać komputer. Oto przykład:

$T(n)=cn^{2}$

c, jak wspomnieliśmy, charakteryzuje tutaj jakość kodu oraz parametry komputera. Wzór ten możemy odczytać następująco: jeżeli liniowo zwiększamy ilość danych, czas wykonywania algorytmu rośnie kwadratowo. Inny algorytm rozwiązujący ten sam problem może być opisany wzorem $T(n)=cn$. Poniżej prezentujemy tabelkę pokazującą, jak wydłuża się czas działania obu algorytmów w zależności od rozmiaru danych wejściowych:

n	1	2	3	4	5	6	7	8	9	10
$T(n)=cn^{2}$	c	4c	9c	16c	25c	36c	49c	64c	81c	100c
$T(n)=cn$	c	2c	3c	4c	5c	6c	7c	8c	9c	10c

Z tabelki jasno widać, że drugi z algorytmów cechuje się wyższą wydajnością. Dla danych rozmiaru 7 wykona się on szybciej, niż algorytm pierwszy dla danych rozmiaru 3. Dla ostatniego argumentu w tabelce - 10 - jest on dziesięciokrotnie szybszy, a im dalej będziemy szli, tym bardziej różnica będzie się pogłębiać.

Okazuje się, że nie zawsze rozmiar jest jedynym czynnikiem, od którego zależy szybkość działania. Niektóre algorytmy bowiem dla pewnych szczególnych danych mogą np. znacząco przyspieszyć, a z kolei inne dane mogą być przetwarzane na nich o wiele dłużej, niż wynika to z naszych obliczeń. W takim przypadku T(n) opisuje najgorszy przypadek zwany też pesymistycznym czasem wykonania - jest to jednak sytuacja skrajna, wobec czego można także zdefiniować najlepszy możliwy przypadek lub średni czas wykonywania. Nie dajmy się przy tym zwieść pozorom. Stawianie założenia, że wszystkie rodzaje danych są jednakowo prawdopodobne, może prowadzić do nieprzewidzianych rezultatów.

Notacja "dużego O" i "dużej Ω"

Załóżmy, że mamy dwa algorytmy, o których wiemy, że:

$T_{1}(n)=c(n+1)^{2}$

$T_{2}(n)=c((n+3)^{2}-2)$

Oczywiście można tutaj bez większych problemów określić, który z nich jest lepszy, po prostu obliczając wartości obu z nich dla kilku dowolnych argumentów. Jednak na dłuższą metę posługiwanie się takimi wzorami bywa po prostu uciążliwe, nie mówiąc już o niezwykłym zadaniu ich wyznaczenia poprzez studiowanie opisu algorytmu. Przy bardziej rozbudowanych algorytmach sprawa komplikuje się do tego stopnia, że możemy mieć nawet trudności z określeniem jakości każdego z nich. Dlatego do porównywania złożoności algorytmów stosuje się nieco inną notację zwaną notacją "dużego O".

Wykres 1: Notacja "dużego O"

Mówiąc mniej matematycznym językiem, zawsze jesteśmy w stanie znaleźć taką stałą c oraz taki argument $n_{0}$, że dla wszystkich kolejnych argumentów "czas" wykonywania algorytmu opisanego funkcją T(n) będzie zawsze mniejszy lub równy od "czasu" opisanego funkcją f(n).

Spróbujmy to przenieść na grunt podanych powyżej dwóch funkcji. Dla $T_{1}(n)$ mamy $T_{1}(n)=O(n^{2})$ oraz $c=5,n_{0}=1$. Faktycznie, dla każdego n większego lub równego 1 zachodzi nam nierówność $(n+1)^{2}\leq 5n^{2}$. Dla $T_{2}(n)$ mamy także $T_{2}(n)=O(n^{2})$, ponieważ dla c = 5 i $n_{0}=3$ zachodzi nierówność $(n+3)^{2}-2\leq 5n^{2}$. Okazuje się zatem, że oba te algorytmy charakteryzują się tym samym rzędem złożoności, zatem dla identycznego rozmiaru danych powinny wykonywać się w podobnym czasie. Funkcja f(n) stanowi tutaj górne ograniczenie tempa wzrostu (innymi słowy: algorytm nigdy nie wykona się wolniej), co pokazuje wykres 1. Czerwona krzywa to pierwsza z przedstawionych powyżej funkcji, zielona - druga, a niebieska to funkcja $f(n)=n^{2}$.

Na oznaczenie dolnej granicy tempa wzrostu (algorytm nigdy nie wykona się szybciej) wprowadzona została notacja "dużej Ω", której definicja jest następująca:

Rząd złożoności

Dobór algorytmu o odpowiedniej złożoności zależy od kilku czynników, m.in. rozmiaru danych oraz mocy komputera. Jeśli mamy dane dwa algorytmy o złożoności sześciennej: $5n^{3}$ oraz kwadratowej: $100n^{2}$, to mimo pozornej przewagi drugiego z nich, zauważmy, że dla n < 20 działający w czasie sześciennym algorytm okaże się szybszy! Naukowcy zajmujący się algorytmami oraz teorią obliczeń podzielili problemy na kilkanaście klas złożoności. Najważniejsze z nich to:

• Problemy P - są to problemy łatwo obliczalne, ich rozwiązanie można znaleźć w czasie wielomianowym (np. $n^{2}$, $n^{6}$).
• Problemy NP - są to problemy trudno obliczalne, ich rozwiązanie można najwyżej sprawdzić w czasie wielomianowym (ale już nie rozwiązać w tym czasie).

Wiadomo, że wszystkie problemy P są też problemami NP, natomiast w drugą stronę sprawa jest nierozstrzygnięta. Jest to jedno z wielkich nierozwiązanych zagadnień matematycznych. Wśród problemów NP można wyróżnić jeszcze kilka podklas. Na szczególną uwagę zasługują problemy NP-zupełne. Ich właściwością jest to, że można do niego w czasie wielomianowym zredukować każdy inny problem NP-zupełny. Znaczy to tyle, że gdyby ktoś znalazł algorytm rozwiązujący w czasie wielomianowym jeden problem NP-zupełny, automatycznie dałoby się w podobnym czasie rozwiązać je wszystkie. Dotychczas jednak wszystkie wymyślone algorytmy mają znacznie większy rząd złożoności, niż większość ludzi jest w stanie zaakceptować, np. n! albo wykładniczy $2^{n}$.

Istnieje też grupa problemów nierozwiązywalnych algorytmicznie.

Rząd złożoności, a moc komputera

Przełóżmy to teraz na praktykę. Łatwo sprawdzić, że wzrost mocy komputera powoduje znaczący przyrost szybkości jedynie dla algorytmów o niskim rzędzie złożoności, np. liniowym n czy logarytmicznym n log n. Załóżmy, że mamy dwa komputery A i B oraz drugi z nich jest dziesięciokrotnie szybszy od pierwszego. Każdemu z nich dajemy 100 sekund na rozwiązanie czterech problemów algorytmicznych o różnej złożoności i obserwujemy, z jakim rodzajem danych wejściowych poradzi sobie każdy z nich.

Algorytm	Komputer A	Komputer B	Przyrost
$10n$	10	100	10
$4n^{2}$	5	15	3
$n^{3}$	4	10	2,5
$2^{n}$	6	10	1,6

Widzimy teraz, że zwiększenie mocy komputera miało najbardziej znaczący wpływ na algorytm liniowy, podczas gdy dla najbardziej zasobożernego algorytmu wykładniczego zaobserwowaliśmy najmniejszy przyrost. Wynika z tego wniosek, że postęp technologiczny ma sens jedynie dla algorytmów o niskim rzędzie złożoności.

Podsumowanie

Rozdział ten ma charakter jedynie ogólnego wprowadzenia do problemu, abyś nie czuł się zagubiony, widząc używane w tym podręczniku pojęcia w stylu element można odnaleźć w czasie liniowym oraz miał świadomość, od czego zależy wydajność algorytmu, a tym samym tworzonych przez Ciebie programów. Po zaznajomieniu się z tym rozdziałem, powinieneś wiedzieć:

• Co to jest złożoność obliczeniowa oraz pamięciowa
• Czym jest notacja dużego O oraz dużej Ω
• Jakie są podstawowe klasy złożoności obliczeniowej
• Jak złożoność obliczeniowa przekłada się na faktyczną wydajność programu

Jeżeli jesteś dalej zainteresowany tym zagadnieniem, polecamy zajrzeć do książek wymienionych w bibliografii.