5996833055

Najczęściej spotykane złożoności czasowe algorytmów:

1)    log(n) - występuje, np. dla algorytmów, w których zadanie rozmiaru n zostaje sprowadzone do zadania rozmiaru n/2 + pewna stała liczba działań ( np. przeszukiwanie binarne uporządkowanego ciągu)

2)    n - występuje, np. dla algorytmów, w których jest wykonywana pewna stała liczba działań dla każdego z n elementów danych wejściowych (np. algorytm Homera wyznaczania wartości wielomianu)

3)    n*log(n) - występuje, np. dla algorytmów, w których zadanie rozmiaru n zostaje sprowadzone do dwóch podzadań rozmiaru n/2 + pewna liczba działań liniowa w n (np. niektóre metody sortowania - quicksort)

4)    n² - występuje, np. dla algorytmów w których jest wykonywana pewna stała liczba działań dla każdej pary elementów danych wejściowych (podwójna instrukcja iteracyjna, np. operacje na tablicach)

5)    2" - występuje, np. dla algorytmów, w których jest wykonywana stała liczba działań dla każdego podzbioru danych wejściowych

6)    n! - występuje, np. dla algorytmów, w których jest wykonywana stała liczba działań dla każdej permutacji danych wejściowych

Czas działania algorytmu/ programu o danym rozmiarze danych

n silnie zależy od złożoności algorytmu ( T = lps ):

	10	20	30	40	50	60
n	0,00001 s	0.000 02s	0.000 03 s	0.000 04 s	0.000 05 s	0,000 06
n^:	0,000 1 s	0,000 4s	0.000 09 s	0,001 6s	0,002 5 s	0.003 6s
n^3	0,001 s	0,008 s	0,027 s	0,064 s	0,125 s	0,216 s
2"	0,001 s	l.Os	17,9 min	12,7 dni	35,7 lat	366 w
3"	0,59 s	58 min	6,5 lal	3855 w	200 • 10^6 w	1,3*10“ w
n!	3,6 s	768 w	8,4*10^16 w	2,6* I0^J" w	9.6*10^48 w	2,6 10“ w