Algorytmy i programowanie  8
Złożoność obliczeniowa
Relacja z"
Niech f (n) i g (n) będą funkcjami rozbiegającymi do nieskończoności gdy n ". Mówimy,
że funkcja f (n) rośnie wolniej niż g (n) , co zapisujemy f (n) z" g (n) wtedy i tylko wtedy gdy
f (n)
lim = 0.
n"
g (n)
Notacja asymptotyczna
Dla danej funkcji g (n) oznaczamy:
" Ś (g (n)) = {f (n) : "c1,c2"n0 takie, że "n n0 0 c1g (n) f (n) c2g (n)}
" O (g (n)) = {f (n) : "c"n0 takie, że "n n0 0 f (n) cg (n)}
" &! (g (n)) = {f (n) : "c"n0 takie, że "n n0 0 cg (n) f (n)}
Fakt
Dla każdych dwóch funkcji f (n) i g (n) zachodzi zależność f (n) = Ś (g (n)) wtedy i tylko
wtedy, gdy f (n) = O (g (n)) i f (n) = &! (g (n)) .
Twierdzenie o rekurencji uniwersalnej
Niech a 1 i b 1 będą stałymi, f (n) będzie pewną funkcją a T (n) będzie zdefiniowane dla
nieujemnych liczb całkowitych przez rekurencję:

n
T (n) = aT + f (n)
b

n n n
gdzie oznacza lub . Wtedy funkcja T (n) może być ograniczona asymptotycznie w
b b b
następujący sposób:

" jeśli f (n) = O nlogb a- dla pewnej stałej > 0, to T (n) = Ś nlogb a ,

" jeśli f (n) = Ś nlogb a , to T (n) = Ś nlogb a ln n ,


n
" jeśli f (n) = &! nlogb a+ dla pewnej stałej > 0 oraz jeśli af cf (n) dla pewnej
b
stałej c < 1 i wszystkich dostatecznie dużych n, to T (n) = Ś (f (n)) .
Zadania
1. Uszeregować poniższe funkcje według relacji z":
" "
53
n2, n, log n, n!, 1, n, log10 n, 2n, nn
2. Korzystając z metody rekurencji uniwersalnej podaj oszacowania asymptotyczne dla poniż-
szych rekurencji:

n
a) T (n) = 9T + n
3

n
b) T (n) = 4T + n
4

2n
c) T (n) = T + 1
3

n
d) T (n) = 4T + n2
2

n
e) T (n) = 3T + n ln n
3

n
f) T (n) = 4T + n3
2

n
3. Czas działania algorytmu A jest opisany przez rekurencję T (n) = 7T + n2, a konku-
2

n
rencyjnego algorytmu A przez T = aT + n2. Jaka jest największa liczba całkowita a, przy
4
której A jest asymptotycznie szybszy niż A?
4. Algorytm sortowania przez zliczanie działa na trzech tablicach n elementowych: A [1..n]
zawierającej nieposortowany ciąg, B [1..n] , w której zwracany jest posortowany ciąg elementów
z A oraz pomocniczej tablicy C [1..k] . Istotnym założeniem jest, że elementy w tablicy A są
wszystkie różne i ze zbioru {1, 2, . . . , k}
procedure SortowaniePrzezZliczanie (A, B, n, k)
for i �! 1 to k
do C [i] �! 0
for i �! 1 to n
do C [A [i]] �! 1
for i �! 2 to k
do C [i] �! C [i] + C [i - 1]
for i �! 1 to n
do B [C [A [i]]] �! A [i]
a) Oszacować złożoność tego algorytmu.
b) Opracować wersję tego algorytmu, gdy dopuścimy powtórzenia w tabeli A.