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 n₀, iż dla każdego n większego lub równego n₀ funkcja f(n) jest niewiększa od iloczynu c^xg(n)

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

• notacja Θ (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(n²)

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(n³), O(n⁴)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log₂n)

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 log₂n)

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(2ⁿ), O(n!)

Złożoność obliczeniową O(2ⁿ) 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(2ⁿ) na tych dwóch komputerach

Czas wykonania algorytmu
Rozmiar danych	20	50	100	200
Komp 1	1,05 sekund	35,7 lat	40169423 mld lat	5^x10^37mld lat
Komp 2	10^-6sekund	1126 sekund	40,17 mld lat	5^x10^31mld lat

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ć

Porównanie klas złożoności obliczeniowych
Klasa złożoności obliczeniowej O()	Nazwa klasy złożoności obliczeniowej	Cechy algorytmu
O(1)	Stała	działa prawie natychmiast
O(log2n)	Logarytmiczna	niesamowicie szybki
O(n)	liniowa	szybki
O(nlog2n)	liniowo-logarytmiczna	dosyć szybki
O(n^2)	kwadratowa	wolny dla dużych n
O(n^3)	sześcienna	wolny dla większych n
O(2^n), O(n!)	wykładnicza	nierealizowalny dla większych n

---