algorytmy_i_struktury_danych:zlozonosc

# Definicja złożoności obliczeniowej

Złożoność obliczeniowa algorytmu - jest to ilość zasobów komputera jakiej potrzebuje dany algorytm. Pojęcie to wprowadzili J. Hartmanis i R. Stearns. Najczęściej przez zasób rozumie się czas oraz pamięć - dlatego też używa się określeń “złożoność czasowa” i “złożoność pamięciowa”.

Za jednostkę złożoności pamięciowej przyjmuje się pojedyncze słowo maszyny (np. Bajt).

## Złożoność czasowa

W przypadku złożoności czasowej nie można podać bezpośrednio jednostki czasu, np. milisekundy, bowiem nie wiadomo na jakiej maszynie dany algorytm będzie wykonywany. Dlatego też wyróżnia się, charakterystyczną dla algorytmu, operację dominującą. Liczba wykonań tej operacji jest proporcjonalna do wykonań wszystkich operacji.

Na złożoność czasową składają się dwie wartości: pesymistyczna, czyli taka, która charakteryzuje najgorszy przypadek działania oraz oczekiwana. Dla oceny algorytmu można wyznaczyć funkcję kosztu wykonania algorytmu. W zależności od sytuacji za jednostkowy krok obliczeniowy do wyznaczania kosztu przyjmuje się: operację arytmetyczną (algorytmy numeryczne), osiągnięcie kolejnego elementu struktury danych (algorytmy operujące na strukturach danych), jedno przesunięcie głowicy dysku (bazy danych). Rozróżnia się koszt maksymalny, średni ewentualnie minimalny.

Najczęściej algorytmy mają złożoność czasową proporcjonalną do funkcji:

Złożoności wielomianowe:

- (n) - liniowa np. u(n) = 230n
- (n2) - kwadratowa np. u(n) = 12n2 + 135n - 23
- (n3) - sześciena np. u(n) = n3 + 20n2 - 19n + 1

Złożoności ograniczone przez wielomian:

- (log n) - logarytmiczna np. 3log (n+1) - 2
- (nlog n) - quasiliniowa np. u(n) = 3nlog (n+1) - 2

Złożoności niewielomianowe:

- NP-zupełna
- (an) - wykładnicza np. u(n) = en + n13 - n2
- silnie NP-zupełna
- NP-trudna

Rzędy wielkości funkcji:

(def.) Rząd wielkości służy do opisu czasu działania algorytmu. Istnieją 3 notacje służące do tego celu.

# Notacje

## Notacja O (omikron)

Notacja O (omikron) Jest to ograniczenie funkcji od góry. Gdy mówimy, że pewna f(n) funkcja jest rzędu g(n), co zapisujemy f(n)=O(g(n)), znaczy to, że istnieje taki argument n0, od którego począwszy dla każdego niemniejszego od n0 wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c.

Na prawo od punktu od n0 funkcja f(n) znajduje się pod funkcją c·g(n), czyli jest przez nią ograniczona z góry. Jest to asymptotyczna granica górna. Służy do szacowania czasu działania algorytmu w przypadku.pesymistycznym.

/* O notacji O nieco inaczej: Ilość operacji potrzebnych do wykonania naszego zadania jest zależna od ilości danych, na jakich ma operować. Jeśli liczbę elementów oznaczymy przez n, możemy powiedzieć, że złożoność algorytmu jest jakąś funkcją f(n). Ponieważ taka funkcja może być bardzo skomplikowana, warto wprowadzić pewne ogólne oznaczenie klasy złożoności. Właśnie do tego służy notacja dużego O.

Oto niektóre najpopularniejsze klasy złożoności ułożone w kolejności od najlepszych (wymagających najmniej operacji) do najgorszych (wymagających najwięcej operacji):

Złożoność stała

O(1) Oznacza, że ilość operacji jest stała i nie zależy od ilości danych, na jakich operujemy.

Złożoność logarytmiczna

O(log n) Występuje wtedy, gdy zbiór jest dzielony na coraz to mniejsze części.

Złożoność liniowa

O(n) Oznacza, że ilość operacji do wykonania jest wprost proporcjonalna do ilości danych, np. kiedy trzeba przebiegnąć po wszystkich elementach zbioru.

Złożoność kwadratowa

O(n2) Oznacza, że ze wzrostem ilości elementów ilość potrzebnych operacji wzrasta bardzo szybko, np. kiedy trzeba przebiegnąć po wszystkich elementach, a dla każdego z nich jeszcze raz przebiegać po wszystkich.

*/

## Notacja Θ (theta)

Notacja Θ (theta) Notacja ta ogranicza funkcję f(n) od góry, tak jak notacja O oraz dodatkowo od dołu. Oznacza to, że jeżeli f(n)=Θ(g(n)) to istnieje taki argument n0, od którego począwszy dla każdego argumenu od niego niemniejszego:

wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c1 wartości funkcji f(n) są niemniejsze od wartości funkcji g(n) z dokładnościądo stałej c2

Na prawo od punktu od n0 funkcja f(n) znajduje się pod funkcją c1·g(n), czyli jest przez nią ograniczona z góry i nad funkcją c2·g(n), czyli jest przez nią ograniczona z dołu Jest to asymptotyczne oszacowanie dokładne.

## Notacja Ω (omega)

Notacja Ω (omega) Notacja ta ogranicza funkcję f(n) od dołu. Oznacza to, że jeśli f(n)=Ω(g(n)) to istnieje taki argument n0, od którego począwszy dla każdego argumenu od niego niemniejszego funkcja f(n) jest niemniejsza niż g(n) z dokładnościądo stałej c:

Na prawo od punktu od n0 funkcja f(n) znajduje się nad funkcją c·g(n). Jest to asymptotyczna granica dolna. Służy więc do oszacowania działania algorytmu w najlepszym przypadku.

Przykład 2 rodzajów sortowania wraz z analizą w excelu

Inne źródła informacji:

Zlożoność obliczeniowa z algorytm.org