Złożoność obliczeniowa

Głównym celem złożoności obliczeniowej jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Zasobami są np.: czas, pamięć lub liczba procesorów.

Złożoność obliczeniowa algorytmów

Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też złożoności pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od danych wejściowych z zakresu danego zagadnienia.

Przykładowo można by rozpatrzyć rozkład liczb na czynniki pierwsze. Przewidzieć można, że (niezależnie od zastosowanego algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Tę cechę podziela większość zagadnień obliczeniowych – im większe rozmiary danych wejściowych, tym więcej zasobów (czasu, procesorów, pamięci) jest koniecznych do wykonania danych obliczeń. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.

Złożoność obliczeniowa: Złożoność obliczeniowa algorytmu określa liczbę zasobów komputerowych potrzebnych do wykonania tego algorytmu.

Typy złożoności obliczeniowej:

Złożoność pesymistyczna- liczba zasobów komuterowych potrzebnych przy wprowadzeniu "najgorszych" danych wejściowych.
Złożoność oczekiwana- liczba zasobów komputerowych potrzebnych przy wprowadzeniu "typowych" danych wyjściowych.

Złożoność czasowa

Złożoność czasowa pozwala oszacować czas potrzebny do wykonania algorytmu.

Jednostką złożoności czasowej jest wykonanie jednej operacji dominującej, to jest operacji charakterystycznej dla danego algorytmu (najczęściej występującej).

Operacjami dominującymi mogą być:

dodawanie i mnożenie w algorytmów numerycznych
porównanie i przestawienie elementów w algorytmów porządkujących

Złożoności algorytmów:

Złożoność stał 0(1): Algorytm wykonuje stałą liczbę operacji dominujących bez względu na rozmiar danych wejściowych.
Złożoność logarytmiczna 0(log n): Taką złożoność mają algorytmy, w których problem postawiony dla danych rozmiaru n da się sprowadzić w pesymistycznym przypadku do problemu z rozmiarem danych o połowę mniejszym.
Złożoność liniowa 0(n): Taką złożoność mają na przykład algorytmy, które dla każdej danej wykonują w pesymistycznym przypadku stałą liczbę operacji podstawowych. Dwukrotny wzrost ilości danych powoduje dwukrotny wzrost ilości wykonywanych operacji.
Złożoność liniowo-logarytmiczna 0( n log(n)): Taka złożoność mają, np. logarytmy, w których problem postawiony dla danych rozmieru n da się sprowadzić w liniowej liczbie operacji do rozwiązania dwóch problemów o rozmiarze n/2.
Złożoność kwadratowa 0 (n²): Dotyczy algorytmów w których dla każdej pary danych wejściowych wykonywana jest stała liczba operacji dominujących ( zwykle są to algorytmy z podwójnymi pętlami ).
Złożoność wykładnicza 0 ( 2ⁿ), 0 (n!): Algorytmy bardzo wolne, ich realizacja w pesymistycznych warunkach jest niewykonalna nawet dla niewielkiego rozmiaru danych.