DSC01320 (2)

Oszacujmy liczbę operacji w naszych algorytmach:

•    Dla algorytmu iteracyjnego ok. n

o Dla algorytmu rekurencyjnego ok. 2ⁿ (np. n=10; 2¹⁰=1024)

Zagadnieniem określania czasu obliczeń zajmują się szczegółowo informatycy.

Wprowadzili oni pojęcie złożoności algorytmu tj. zależności liczby wykonywanych operacji od rozmiaru danych (n).

Wyróżnia się algorytmy m.in. o złożoności:

g? wykładniczej np. 2ⁿ (algorytm rekurencyjny obliczeń F(n))

•    wielomianowej (czas obliczeń zależy od potęgi rozmiaru problemu, np. liniowo - 3n, kwadratowo - 2n²)

•    Logarytmiczna np. log₂n (b. dobra zbieżność)