Złożoność obliczeniowa algorytmów

Przez złożoność obliczeniowa algorytmów rozumiemy ilość zasobów niezbędnych do wykonania algorytmu. Przez zasoby rozumie się zwykle czas (złożoność czasowa) i zajętość pamięci operacyjnej (złożoność pamięciowa).

Złożoność czasowa

Czas działania algorytmu zależy od samego algorytmu oraz od szybkości działania komputera, rodzaju i wielkości danych. W celu uniezależnienia się od konkretnego komputera przyjmuje się, ze zamiast czasu określa się ilość wykonywanych operacji elementarnych zakładając jednakowy czas ich wykonania. Za operacje elementarne dla algorytmu napisanego w PASCALU przyjmuje się:

·      operacje arytmetyczne, logiczne, relacyjne

·      podstawienie pod zmienną prostą lub wskaźnikową

·      indeksowanie, odwołanie do pola rekordu

·      inicjalizacja wywołania procedury

·      przekazanie wartości parametru aktualnego

·      instrukcja skoku wejścia / wyjścia

Najczęściej stosuje się złożoność asymptotyczną, która mówi o tym jak złożoność kształtuje się dla bardzo dużych, granicznych rozmiarów danych wejściowych

Trzy rodzaje złożoności asymptotycznej:

-        notacja O (omikron) – ma największe znaczenie w teorii złożoności obliczeniowej. Zapis f(n) = O(g(n)) czytamy: funkcja f jest co najwyżej rzędu g, jeśli istnieje taka stała rzeczywista c i liczba naturalna n0, iż dla każdego n większego lub równego n0 funkcja f(n) jest niewiększa od iloczynu cxg(n)

-        notacja W (omega) – gdy funkcja g(n) ogranicza funkcję f(n) od dołu

-        notacja Q (theta) – gdy funkcja g(n) ogranicza funkcje f(n) od góry i od dołu

Złożoność obliczeniowa stała - O(1)

Algorytm wykonuje stałą ilość operacji dominujących bez względu na rozmiar danych wejściowych.

Złożoność obliczeniowa liniowa - O(n)

Dla każdej danej algorytm wykonuje stałą ilość operacji dominujących. Czas wykonania jest proporcjonalny do liczby n danych wejściowych.

Złożoność obliczeniowa kwadratowa - O(n2)

Algorytm dla każdej danej wykonuje ilość operacji dominujących proporcjonalną do liczby wszystkich przetwarzanych danych. Czas wykonania jest proporcjonalny do kwadratu liczby Inne złożoności tego typu O(n3), O(n4)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log2n)

W algorytmie zadanie rozmiaru n da się sprowadzić do zadania rozmiaru n/2. Typowym przykładem jest wyszukiwanie binarne w zbiorze uporządkowanym. Sprawdzenie środkowego elementu pozwala określić, w której z dwóch połówek zbioru może znajdować się poszukiwany element.

Złożoność obliczeniowa liniowo logarytmiczna - O(n log2n)

Zadanie rozmiaru n daje się sprowadzić do dwóch podzadań rozmiaru n/2 plus pewna ilość operacji, których liczba jest proporcjonalna do ilości danych n. Tego typu złożoność obliczeniową posiadają dobre algorytmy sortujące

Złożoność obliczeniowa wykładnicza - O(2n), O(n!)

Złożoność obliczeniową O(2n) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdego podzbioru n danych wejściowych.

Złożoność obliczeniową O(n!) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdej permutacji n danych wejściowych.

Złożoność obliczeniowa wykładnicza jest bardzo niekorzystna, ponieważ czas wykonania rośnie szybko wraz ze wzrostem liczby danych wejściowych. Dla porównania załóżmy, iż posiadamy dwa komputery. Pierwszy potrafi wykonać milion operacji dominujących w ciągu sekundy. Drugi jest superkomputerem i potrafi tych operacji wykonać milion razy więcej (bardzo optymistyczne założenie), czyli 1000 miliardów w ciągu sekundy. W poniższej tabeli zebraliśmy dane o czasie wykonania algorytmu klasy O(2n) na tych dwóch komputerach

Z tabelki jasno wynika, iż zastosowanie superszybkiego komputera niewiele pomaga algorytmowi. Czas wyznaczenia rozwiązania może stać się niewyobrażalnie duży (już dla n = 100 w obu przypadkach raczej nie doczekamy się wyników). Dlatego algorytm o wykładniczej złożoności obliczeniowej uważa się za wewnętrznie nierealizowalny i należy go unikać