alg(1).pdf

(76 KB) Pobierz
Zajęcia
Algorytmy i programowanie
Analiza algorytmów. Szacowanie złożoności obliczeniowej.
Złożoność obliczeniowa (czasowa) algorytmu
- zależność pomię-
dzy rozmiarem danych wejściowych a liczbą operacji elementarnych wyko-
nywanych w trakcie przebiegu algorytmu (podawana jako funkcja rozmiaru
danych).
Operacje elementarne to np. liczba porównań dwóch liczb w algorytmie
sortowania, liczba mnożeń w algorytmie obliczania silni, liczba dzieleń w
algorytmie sprawdzania czy dana liczba jest pierwsza, ogólna liczba operacji
arytmetycznych wykonywanych przez dany algorytm itp..
Złożoność obliczeniowa jest jednym z najważniejszych parametrów cha-
rakteryzujących algorytm. Decyduje ona o efektywności całego programu.
Podstawowymi zasobami systemowymi uwzględnianymi w analizie algoryt-
mów są czas działania (złożoność obliczeniowa algorytmu) oraz obszar zaj-
mowanej pamięci (złożoność pamięciowa algorytmu). Złożoność pamięciowa
wynika z liczby i rozmiaru struktur danych wykorzystywanych w algorytmie.
Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego
przypadku lub złożoności średniej. Złożoność najgorszego przypadku nazy-
wamy złożonością pesymistyczną - jest to maksymalna złożoność dla danych
o zadanym rozmiarze
n.
Złożoność średnia lub oczekiwana to średnia war-
tość złożoności dla wszystkich problemów rozmiaru
n.
Najczęściej algorytmy
mają złożoność czasową proporcjonalną do funkcji:
—
—
—
—
—
—
—
—
log(n)- złożoność logarytmiczna,
n
- złożoność liniowa,
n
log(n) - złożoność liniowo-logarytmiczna,
n
2
- złożoność kwadratowa,
n
k
- złożoność wielomianowa, (k
>
2),
2
log
n
- złożoność podwykładnicza,
2
n
- złożoność wykładnicza,
n!
- złożoność wykładnicza
Notacja asymptotyczna
Rząd wielkości służy do opisu czasu działania algorytmu. Istnieją 3 no-
tacje służące do tego celu:
Funkcja asymptotycznie niewiększa
od funkcji
g(n)
to taka funkcja
f
:
N
−→
R,
dla której istnieją
c >
0 i
n
0
∈
N,
że
|f
(n)|
c
· |g(n)|
dla
wszystkich
n n
0
.
Będziemy też często mówić, że
|f
(n)|
c
· |g(n)|
zachodzi dla prawie
wszystkich liczb naturalnych
n.
Zbiór funkcji asymptotycznie niewiększych
niż
g(n)
oznaczamy przez
O(g(n)).
Funkcja asymptotycznie niemniejsza
od funkcji
g(n)
to taka funkcja
f
:
N
−→
R,
dla której istnieją
c >
0 i
n
0
∈
N,
że
c
· |g(n)|
|f
(n)| dla
wszystkich
n n
0
.
Zbiór funkcji asymptotycznie niemniejszych niż
g(n)
oznaczamy przez
Ω(g(n)).
1
Zajęcia
Algorytmy i programowanie
Funkcja asymptotycznie podobna
do funkcji
g(n)
to taka funkcja
f
:
N
−→
R,
dla której istnieją
c
0
, c
1
>
0 i
n
0
∈
N,
że
c
0
· |g(n)| |f
(n)|
c
1
· |g(n)|
dla wszystkich
n n
0
.
Zbiór funkcji asymptotycznie podobnych do
g(n)
oznaczamy przez Θ(g(n)).
A zatem Θ(g(n)) =
O(g(n))
∩
Ω(g(n)).
Odpowiednio w stosunku do wcześniej wypisanych funkcji powiemy, że
złożoność obliczeniowa algorytmu wynosi (lub algorytm „działa w czasie”)
O(log(n)), O(n), O(n
log(n)), itd.
Gdzie np. log
n
=
O(n)
,
n
2
= Ω(n) ,
n
=
O(n)
,
n
= Ω(n) ,
n
= Θ(n) ,
20n = Θ(n).
Zadania na ćwiczenia
Zadanie 0
Jaka jest złożoność obliczeniowa algorytmu sortowania bąbelkowego ?
Sortowania przez zliczanie ?
Zadanie 1
Uporządkować rosnąco wg rzędu następujące funkcje:
2
n!
,
n
2
, (2009!)n
2
,
n
3
−
n
2
,
n
3
,
n
3
+
n
2
, 2
n
,
n
2009!
,
n!
,
n
log
n
, log
n.
Zadanie 2
Udowodnij przechodność:
f
(n) = Θ(g(n)) i
g(n)
= Θ(h(n))
⇒
f
(n) = Θ(h(n))
Zadanie 3
Znajdź i wykaż (udowodnij) zależności pomiędzy funkcjami w notacji
asymptotycznej:
— 2n w odniesieniu do (20!)n,
—
n
2
−
n
w odniesieniu do
n
2
+
n,
— log
2
n
w odniesieniu do
n,
— 3
n
w odniesieniu do 2
n
—
n!
w odniesieniu do 2
n
Zadanie 4
Podaj złożoność algorytmów rekurencyjnych:
Wyliczającego silnię, fibonacciego ? Wyszukiwania binarnego, sortowania
przez scalanie ?
Zadanie 5
Podaj złożoność funkcji rekurencyjnych:
n
T
(n) = 2T ( ) + 5n
−
15
2
n
T
(n) = 16T ( ) +
n
lg
n
4
n
T
(n) = 2T ( ) +
n
lg
n
2
2
Zajęcia
Literatura
Wykład Asymptotyka
Algorytmy i programowanie
3

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin