490574689

WYKŁAD

ZŁOŻONOŚĆ ALGORYTMÓW

„Ilość zasobów komputera niezbędna do wykonania algorytmu”:

-    czas działania (T) na etapie wykonania - złożoność czasowa (zależy od ilości operacji do wykonania i szybkości komputera)

-    zajętość pamięci (P) - złożoność pamięciowa

a)    jednoznaczna jednostka (np. Byte, słowo maszynowe, komórka)

b)    złożoność: P(n)

c)    traci na znaczeniu (np. ceny RAM maleją, ale nie do końca - przetwarzanie obrazów),

np. P(n) = 2ⁿ (dla n = 150; liczba komórek pamięci przekracza liczbę atomów we wszechświecie).

-    rozmiar zadania (n) - liczba pojedynczych danych w zadaniu

-    T i P - funkcje od n (są związane ze sobą)

ZŁOŻONOŚĆ CZASOWA

jednostka miary: liczba (szacunek operacji) operacje dominujące (zliczane) złożoność pesymistyczna i oczekiwana złożoność praktyczna T(n) złożoność teoretyczna - klasa algorytmu

0(n) = 0(T(n)), gdzie O - rząd funkcji T(n) asymptotyczny n - rozmiar zadania

np.

T(n)	O
n+1 n^2-n+1 2"+n^2+4	3'''^cO o o

KLASA ALGORYTMU - przykład

-    obliczanie wartości wielomianu (zwykłe)

W(x, n) = a_nxⁿ+ a„_ix +...+ a_tx+ a₀ operacja dominująca - mnożenie złożoność praktyczna:

n+1    1    1

T(n) = n = (n-1)+...+ 1=    =    ^— n²+ ~n

2    2    2

klasa algorytmu 0(n) = 0(n²)

-    obliczanie wartości wielomianu - schemat Homera W(x, n) = ao+x(a|+x(a₂+...+ x(a_n_i+x_an)...)) operacja dominująca - mnożenie

złożoność praktyczna:

T(n) = n

klasa algorytmu 0(n) = O(n)