Złożoność obliczeniowa Zadania 2

background image

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:

background image

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

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.


Wyszukiwarka

Podobne podstrony:
Złożoność obliczeniowa Zadania 1
złożoność algorytmów zadanie
kozik,projektowanie algorytmów,TEORIA ZŁOŻONOŚCI OBLICZENIOWEJ
SDiZO5b, Struktury danych i złożoność obliczeniowa
lichtenstein, struktury?nych i złożoność obliczeniowa,Badanie?ektywności algorytmów pseudowielomiano
obliczenia zadania 2
Algorytmy wyklady, Złożoność obliczeniowa algorytmów
MIARY ZLOZONOSCI OBLICZENIOWEJ
ćw3 Analiza złożoności obliczeniowej
obliczenia zadania 5
SDiZO5a, Struktury danych i złożoność obliczeniowa
SDiZO3, Struktury danych i złożoność obliczeniowa
10. Problemy obliczeniowe i zadania, wykłady Apostoluka
ćw2 Analiza złożoności obliczeniowej
10. Problemy obliczeniowe i zadania
Pochodne funkcji zlozonych Za Zadanie domowe id 810241
Algorytmy i struktury danych 02 Rekurencja i złożoność obliczeniowa

więcej podobnych podstron