ZŁOŻONOŚĆ OBLICZENIOWA

Na złożoność obliczeniową składają się:

Złożoność czasowa - określa ilość czasu, którą potrzebuje algorytm na rozwiązanie problemu

Złożoność pamięciowa - określa ilość pamięci, którą potrzebuje algorytm na rozwiązanie problemu

ALGORYTMEM EFEKTYWNIEJSZYM - nazywamy ten algorytm, który rozwiązując ten sam problem ma mniejszą złożoność obliczeniową

Wyróżniamy operacje dominujące algorytmu - te, których ilość decydująco wpływa na czas działania (dla złożoności czasowej) lub na ilość potrzebnej pamięci (przy złożoności pamięciowej)..

Np. W problemie sortowania ciągu liczb czas działania mierzy się ilością wykonanych porównań

Rozpatrujemy pesymistyczną złożoność czasową lub pamięciową dla najbardziej złośliwych danych.

Złożoność czasowa

Niech t(w) - funkcja czasu działania algorytmu na danych w

Pesymistyczna złożoność czasowa to funkcja:

T(n)= max { t(w); gdzie w dowolne poprawne dane wejściowe długości n }

Złożoność pamięciowa

Niech s(w) - funkcja zajmowanej pamięci przez dane w podczas działania algorytmu

Pesymistyczna złożoność pamięciowa to funkcja:

S(n)= max { s(w); gdzie w dowolne poprawne dane wejściowe długości n }

OBLICZANIE ZŁOŻONOŚCI

Przykłady rzędów złożoności:

Log n logarytmiczna

n liniowa

n log n n log n

n^2 kwadratowa

itd.

Funkcja f(n) jest rzędu g(n), (ozn. O(g(n))) jeśli istnieją stałe n0 i c, że:

∀ f(n) ≤ g(n) * c

n ≥ n0

czyli funkcja f(n) jest dla prawie wszystkich n (poza skończoną ilością) ograniczona przez funkcję g(n) pomnożoną przez pewną stałą c.

UWAGA:

Notacja „O” eliminuje składniki wolniej rosnące oraz zaniedbuje czynniki stałe, przez które pomnożone są funkcje.

Przykład:

f(n) = 5n² - 2*n + 2 = O(n²)

Ponieważ: ∀ 5n² - 2n + 2 ≤ 5n²

n ∈ N

Zadanie 1:

Określ rząd funkcji:

1. f(n) = 25*2ⁿ+100*n²

2. f(n) = n logn - 1.44n

3. f(n) = n + 100 log n

4. f(n) = log n¹⁷

Przykłady określania złożoności czasowej:

1. Przeszukiwanie elementów w celu znalezienia danego elementu x

i:=0;

Repeat i:=i+1 until (a[i]=x) or (i=n);

O(n)

2. Jeżeli elementy są wcześniej posortowane, stosujemy metodę połowienia przedziałów

(metoda bisekcji lub przeszukiwania połówkowego)

i:=1;

j:=n;

repeat k:=(i+j) div 2

if x>a[k] then i:= k+1 else j:= k-1

until (x=a[k]) or (i>j);

O(log n)

3. Znajdowanie min i max metodą iteracyjną

min:=a[1];

max:=a[1];

for i:=2 to n do

begin

if min >a[i] then min:=a[i];

if max <a[i] then max:=a[i]

end;

O(n)

Zadanie:

Określ złożoność czasową dla sortowań:

1. Przez proste wybieranie

2. Przez proste wstawianie

3. Bąbelkowe

4. Szybkie

5. Przez scalanie

6. kubełkowe

ABK_Złożoność___________________________________________________________3/3

---