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 ∀

n­n

0

0 ¬ c

1

g (n) ¬ f (n) ¬ c

2

g (n)}

• O (g (n)) = {f (n) : ∃

c

∃

n

0

takie, że ∀

n­n

0

0 ¬ f (n) ¬ cg (n)}

• Ω (g (n)) = {f (n) : ∃

c

∃

n

0

takie, że ∀

n­n

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.