4962385661

Żeby analizować złożoność algorytmu musimy coś wiedzieć o tym jak on będzie wykonywany przez maszynę.

My będziemy zakładać, że programy są wykonywane na maszynie o dostępie swobodnym (RAM): tzn. instrukcje są wykonywane jedna po drugiej (nigdy dwie na raz) i program nie może się modyfikować w trakcie działania.

Czas działania zależy od rozmiaru danych wejściowych. 5 liczb nasz algorytm sortuje szybciej niż 1000. Także dla dwóch ciągów równej długości algorytm może wykonywać różną liczbę instrukcji w zależności od tego jak bardzo różnią się one od ciągu posortowanego. Na ogół, czas działania algorytmu wyrażany jest jako funkcja rozmiaru danych wyjściowych.

1.    Rozmiar danych wejściowych jest to funkcja przyporządkowująca poprawnym danym wejściowym algorytmu liczbę naturalną.

2.    Czas działania algorytmu jest to funkcja przyporządkowująca danym wejściowym liczbę podstawowych operacji wykonywanych przez algorytm na tych danych.

3.    (Pesymistyczna, czasowa) złożoność algorytmu jest to funkcja z N w N przyporządkowująca liczbie naturalnej n najdłuższy czas działania algorytmu na danych o rozmiarze n.

Dla problemu sortowania rozmiar danych to długość ciągu.

nr

1    dla j:=2 do n wykonuj

2    k:=A[j];

3    i:=j-l;

4    dopóki i>0 oraz A[i]>k wykonuj

5    A[i+1] :=A[i] ;

6    i:=i—1;

7    ACi+1] :=k;

czas

n

n-1

n-1

t_2+...+t_n (t_2-l)+...+(t_n-l) (t_2-l)+...+(t_n-l)

n-1

•    tj - liczba wykonań linii 4 przy ustalonym j.

•    tj - jest największy gdy macierz jest uporządkowana w porządku malejącym, wtedy tj = j.

•    T(n) - złożoność algorytmu.

T(n) = 3(n - 1) + n + 2 £(j - 1) + £>' =

3=2    j=2

_n. .    n(n — 1) n(n +1)    3 o 7

_;3(_n—l) + n + 2 ^k ₂    ’+ ^k2 l = -»² + -n-4

To jest ciągle ’za dokładnie’, składniki |n i —4 oraz stała § nie mają większego znaczenia, przy dużych n. To co jest ważne to n². Mówimy, że algorytm sortowania przez wkładanie ma złożoność (pesymistyczną, czasową) 0(n²).

Notacja 0(f(n)). Niech / : N —» N funkcja. Mówimy, że funkcja g : N —» N jest (klasy) 0(f(n)) (piszemy g 6 0(f(ń)) lub wręcz g = 0(f(n))) jeśli istnieją stałe a, b £ R takie, że dla n > b, g(n) < a* f(n) (’g przyjmuje wartości nie większe niż / z dokładnością do stałej’).

6