Algorytmy i programowanie – 8
Złożoność obliczeniowa
Relacja ≺
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) ≺ g (n) wtedy i tylko wtedy gdy
lim
n→∞
f (n)
g (n)
= 0.
Notacja asymptotyczna
Dla danej funkcji g (n) oznaczamy:
• Θ (g (n)) = {f (n) : ∃
c
1
,c
2
∃
n
0
takie, że ∀
nn
0
0 ¬ c
1
g (n) ¬ f (n) ¬ c
2
g (n)}
• O (g (n)) = {f (n) : ∃
c
∃
n
0
takie, że ∀
nn
0
0 ¬ f (n) ¬ cg (n)}
• Ω (g (n)) = {f (n) : ∃
c
∃
n
0
takie, że ∀
nn
0
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ę:
T (n) = aT
n
b
+ f (n)
gdzie
n
b
oznacza
n
b
lub
n
b
. Wtedy funkcja T (n) może być ograniczona asymptotycznie w
następujący sposób:
• jeśli f (n) = O
n
log
b
a−
dla pewnej stałej > 0, to T (n) = Θ
n
log
b
a
,
• jeśli f (n) = Θ
n
log
b
a
, to T (n) = Θ
n
log
b
a
ln n
,
• jeśli f (n) = Ω
n
log
b
a+
dla pewnej stałej > 0 oraz jeśli af
n
b
¬ cf (n) dla pewnej
stałej c < 1 i wszystkich dostatecznie dużych n, to T (n) = Θ (f (n)) .
Zadania
1. Uszeregować poniższe funkcje według relacji ≺:
n
2
,
53
√
n,
log n,
n!,
1,
√
n,
log
10
n,
2
n
,
n
n
2. Korzystając z metody rekurencji uniwersalnej podaj oszacowania asymptotyczne dla poniż-
szych rekurencji:
a) T (n) = 9T
n
3
+ n
b) T (n) = 4T
n
4
+ n
c) T (n) = T
2n
3
+ 1
d) T (n) = 4T
n
2
+ n
2
e) T (n) = 3T
n
3
+ n ln n
f) T (n) = 4T
n
2
+ n
3
3.
Czas działania algorytmu A jest opisany przez rekurencję T (n) = 7T
n
2
+ n
2
, a konku-
rencyjnego algorytmu A
0
przez T
0
= aT
0
n
4
+ n
2
. Jaka jest największa liczba całkowita a, przy
której A
0
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.