Zło
Ŝoność obliczeniowa
Kryteria wyboru algorytmów:
•
czas działania
•
ilo
ść pamięci niezbędnej do wykonania algorytmu dla określonego zbioru danych
wej
ściowych
•
szybko
ść wzrostu zajętości pamięci i czasu obliczeń przy zmianie liczby danych
Rozmiar problemu:
liczba naturalna b
ędąca miarą wielkości danych wejściowych, np.:
•
sortowanie, wyszukiwanie: liczba elementów
•
mno
Ŝenie macierzy: maksymalny rozmiar macierzy
•
analiza grafów: liczba wierzchołków lub kraw
ędzi grafu
Zło
Ŝoność czasowa algorytmu:
Czas wykonania algorytmu jako funkcja rozmiaru problemu (funkcja kosztu
czasowego algorytmu)
T(n), n – rozmiar problemu
Zło
Ŝoność pamięciowa algorytmu:
Funkcja rozmiaru problemu okre
ślająca ilość pamięci potrzebną do realizacji danego
algorytmu
S(n)
Zło
Ŝoność średnia
∑
∈
∈
∈
∈
⋅⋅⋅⋅
====
n
D
d
sr
d
T
d
pr
n
T
)
(
)
(
)
(
•
pr(d) – prawdopodobie
ństwo wystąpienia zestawu danych d
•
D
n
– zbiór zestawów danych rozmiaru n
•
wada – trzeba zna
ć prawdopodobieństwa
Zło
Ŝoność pesymistyczna – dla najgorszego przypadku
T
pes
(n) = max{T(d), d – dane rozmiaru n }
Notacja „O” (order – rz
ąd)
Nieujemna funkcja g(n) jest rz
ędu co najwyŜej funkcji f(n), czyli:
g(n) = O(f(n))
gdy istnieje stała c > 0 taka,
Ŝe:
g(n)
≤≤≤≤
c
⋅⋅⋅⋅
f(n)
dla prawie ka
Ŝdego n
∈
∈
∈
∈
N
•
przy szacowaniu zło
Ŝoności funkcję g(n) moŜna zastąpić funkcją f(n)
Własno
ść:
))
(
(
)
(
))
(
(
)
(
n
h
O
n
f
n
f
O
n
g
====
∧∧∧∧
====
⇓
))
(
(
)
(
n
h
O
n
g
====
Przykład:
)
(
...
2
1
3
2
2
2
n
O
n
====
++++
++++
++++
Dowód:
n
n
n
n
n
n
n
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
====
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
⋅⋅⋅⋅
====
++++
++++
++++
6
1
2
1
3
1
)
1
(
)
2
1
(
3
1
...
2
1
2
3
2
2
2
n
n
n
n
g
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
6
1
2
1
3
1
)
(
2
3
3
)
(
n
n
f
====
3
2
3
6
1
2
1
3
1
n
c
n
n
n
⋅⋅⋅⋅
≤≤≤≤
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
- z definicji
przy c=1:
6
//
6
1
2
1
3
1
3
2
3
⋅⋅⋅⋅
≤≤≤≤
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
n
n
n
n
3
3
2
3
2
//
6
3
2
n
n
n
n
n
⋅⋅⋅⋅
−−−−
⋅⋅⋅⋅
≤≤≤≤
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
n
n
n
n
:
//
4
3
3
2
⋅⋅⋅⋅
≤≤≤≤
++++
⋅⋅⋅⋅
2
4
1
3
n
n
⋅⋅⋅⋅
≤≤≤≤
++++
⋅⋅⋅⋅
- prawdziwe dla ka
Ŝdego n
∈
∈
∈
∈
N,
c.n.d.
np.
•
)
(
log
2
2
2
n
O
n
n
n
====
⋅⋅⋅⋅
++++
•
)
(
log
2
2
n
O
n
n
====
⋅⋅⋅⋅
szacowanie tym lepsze, im funkcje bli
Ŝej siebie
Szacowanie rz
ędu złoŜoności obliczeniowej dla wielomianów
)
(
...
)
(
0
1
2
2
1
1
m
m
m
m
m
m
m
m
n
O
a
n
a
n
a
n
a
n
a
n
P
====
====
++++
⋅⋅⋅⋅
++++
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
−−−−
−−−−
−−−−
−−−−
Dowód:
m
m
m
m
m
m
m
m
m
m
m
m
m
m
n
c
a
a
a
a
n
n
a
n
a
n
a
a
n
a
n
a
n
a
n
a
n
P
⋅⋅⋅⋅
====
++++
++++
++++
++++
⋅⋅⋅⋅
≤≤≤≤
≤≤≤≤
++++
++++
++++
++++
⋅⋅⋅⋅
====
====
++++
⋅⋅⋅⋅
++++
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
≤≤≤≤
−−−−
−−−−
−−−−
−−−−
−−−−
|)
|
|
|
...
|
|
|
(|
)
1
|
|
1
|
|
...
1
|
|
|
(|
|
|
|
|
...
|
|
|
|
)
(
0
1
1
0
1
1
1
0
1
1
1
gdzie
∑
====
====
0
|
|
m
i
i
a
c
czyli:
m
m
cn
n
cf
n
g
n
P
====
≤≤≤≤
====
)
(
)
(
)
(
)
(
)
(
m
m
n
O
n
P
====
c.n.d.
Zasady szacowania zło
Ŝoności czasowych
1.
Koszt całkowity (arytmetyczny) algorytmu – liczba wszystkich operacji (działa
ń)
2.
Operacja dominuj
ąca – liczba takich operacji, potrzebnych do wykonania algorytmu
dla dowolnych danych i na dowolnym komputerze jest proporcjonalna do liczby
wszystkich wykonywanych operacji.
Zło
Ŝ
ono
ść
czasowa:
Zło
Ŝoność czasowa algorytmu A to liczba operacji dominujących potrzebnych do
wykonania algorytmu A zale
Ŝna od rozmiaru problemu.
Przykłady szacowania zło
Ŝoności czasowych
•
Obliczanie warto
ści wielomianu:
0
1
2
2
1
1
...
)
(
a
x
a
x
a
x
a
x
a
x
P
n
n
n
n
n
n
n
++++
⋅⋅⋅⋅
++++
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
−−−−
−−−−
−−−−
−−−−
z definicji:
- rozmiar problemu – n
- pot
ęgowanie zastępujemy mnoŜeniem
- operacje dominuj
ące – dodawanie i mnoŜenie (d i m)
n
L
d
====
++++
++++
++++
++++
−−−−
++++
−−−−
====
1
2
...
)
2
(
)
1
(
n
n
L
m
z pot
ęgowania
n
++++
z mno
Ŝenia
k
k
x
a
⋅⋅⋅⋅
)
(
2
3
2
1
2
3
2
1
1
2
...
)
2
(
)
1
(
)
(
2
2
2
n
O
n
n
n
n
n
n
n
n
n
n
n
n
T
====
++++
====
++++
====
⋅⋅⋅⋅
++++
++++
====
====
++++
++++
++++
−−−−
++++
−−−−
++++
++++
====
)
(
)
(
2
n
O
n
T
====
Przykłady szacowania zło
Ŝoności czasowych
(na podstawie algorytmu)
•
Obliczanie warto
ści wielomianu:
0
1
2
2
1
1
...
)
(
a
x
a
x
a
x
a
x
a
x
P
n
n
n
n
n
n
n
++++
⋅⋅⋅⋅
++++
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
−−−−
−−−−
−−−−
−−−−
ze schematu Hornera
0
1
2
1
)
...
)
)
(...((
)
(
a
x
a
x
a
x
a
x
a
x
P
n
n
n
n
++++
⋅⋅⋅⋅
++++
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
−−−−
−−−−
- rozmiar problemu – n
- operacje dominuj
ące – dodawanie i mnoŜenie (d i m)
na przykład:
0
1
1
)
(
1
a
x
a
x
P
n
++++
⋅⋅⋅⋅
====
====
0
1
2
0
1
2
2
2
)
(
)
(
2
a
x
a
x
a
a
x
a
x
a
x
P
n
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
====
0
1
2
3
3
)
)
((
)
(
3
a
x
a
x
a
x
a
x
P
n
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
====
- liczba dodawa
ń i mnoŜeń:
n
L
d
====
n
L
m
====
)
(
2
)
(
n
O
n
n
T
====
⋅⋅⋅⋅
====
Przykłady szacowania zło
Ŝoności czasowych
(na podstawie schematu blokowego)
Problem: wyszukiwanie danej x w tablicy n-elementowej
n
t
p
d
t
p
K
⋅⋅⋅⋅
++++
++++
++++
++++
====
)
(
operacja dominuj
ąca: t
n
t
n
T
⋅⋅⋅⋅
⋅⋅⋅⋅
====
2
)
(
)
(
)
(
n
O
n
T
====
Przykłady szacowania zło
Ŝoności czasowych
(na podstawie schematu blokowego)
Problem: wyszukiwanie danej x w tablicy n-elementowej
(wersja z wartownikiem)
d
t
p
n
p
d
t
t
t
n
p
d
t
p
K
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
++++
++++
====
====
++++
++++
++++
⋅⋅⋅⋅
++++
++++
++++
====
3
2
)
(
)
1
(
)
(
operacja dominuj
ąca: t
t
n
t
n
T
⋅⋅⋅⋅
++++
⋅⋅⋅⋅
====
3
)
(
)
(
)
(
n
O
n
T
====
Przykłady szacowania zło
Ŝoności czasowych
(na podstawie pseudokodu)
Problem: wyznaczanie iloczynu
m
n
il
⋅⋅⋅⋅
====
z definicji
begin
il := 0;
N := n;
while N > 0 do
begin
il := il + m;
N := N – 1;
end
end
t
n
d
p
t
p
K
++++
⋅⋅⋅⋅
++++
++++
++++
====
)
2
2
(
2
•
operacja dominuj
ąca: dodawanie d, wtedy złoŜoność „dokładna”:
n
d
n
T
2
)
(
====
•
zło
Ŝoność rzędu:
)
(
)
(
n
O
n
T
====
Przykłady szacowania zło
Ŝoności czasowych
(na podstawie pseudokodu)
Problem: wyznaczanie iloczynu
n
m
il
⋅⋅⋅⋅
====
wykorzystuj
ąc bitową postać mnoŜnika
begin
il := 0;
N := n;
S := m;
while N <> 0 do
begin
if Odd(N) then il := il + S;
N := N div 2;
S := 2 * S
end
end
gdzie
0
1
2
1
2
2
...
2
2
2
++++
++++
++++
++++
++++
====
−−−−
−−−−
r
r
r
N
oraz
N
r
2
log
====
)
(
)
(
log
)
2
(
3
2
2
2
n
d
p
t
n
m
p
d
t
t
p
K
n
γγγγ
⋅⋅⋅⋅
++++
++++
++++
⋅⋅⋅⋅
++++
++++
++++
++++
++++
====
gdzie
)
(n
γγγγ
- liczba jedynek w rozwini
ęciu binarnym liczby n
•
operacja dominuj
ąca: dodawanie d
)
(
)
(
n
d
n
T
γγγγ
⋅⋅⋅⋅
====
•
przypadek pesymistyczny: n zło
Ŝone z samych jedynek:
n
n
2
log
)
(
====
γγγγ
•
zło
Ŝoność „dokładna”:
n
d
n
T
2
log
)
(
⋅⋅⋅⋅
====
•
zło
Ŝoność rzędu:
)
(log
)
(
2
n
O
n
T
====
n
1
2
3
4
5
6
7
8
9
10
20
50
100
log
2
n
0
1 1,58
2 2,32 2,58
2,8
3
3,17
3,32
4,32
5,64
6,64
n
1
2
3
4
5
6
7
8
9
10
20
50
100
nlog
2
n
0
2 4,57
8 11,61 15,51 19,65
24 28,53
33,22
86,44 282,19 664,38
n
2
1
4
9
16
35
36
49
64
81
100
400
2500
10000
n
3
1
8
27
64
125
216
343 512
729
1000
8000 125000 1000000
2
n
2
4
8
16
32
64
128 256
512
1024 1048576
10
15
10
30
n!
1
2
6
24
120
720 5040 4032 362880 3628800
2
⋅⋅⋅⋅
10
18
3
⋅⋅⋅⋅
10
64
10
157
Maksymalny rozmiar problemu w czasie:
Zło
Ŝ
ono
ść
1s
1min
1h
n
1000
6
⋅⋅⋅⋅
10
4
3,6
⋅⋅⋅⋅
10
6
nlog
2
n
140
4893
2
⋅⋅⋅⋅
10
5
n
2
31
244
1897
n
3
10
39
153
2
n
9
15
21
1op=0,001s
Problem rozmiaru 10000
Zło
Ŝ
ono
ść
[op]
czas
n
10000
10s
nlog
2
n
13
⋅⋅⋅⋅
10
4
130s
n
2
10
8
28h
n
3
10
12
~32 lata
2
n
2
10000
???
1op=0,001s
Max rozmiar problemu
Zło
Ŝ
ono
ść
1x
przsp. 10x
n
s1
10
⋅⋅⋅⋅
s1
nlog
2
n
s2
10
⋅⋅⋅⋅
s2
dla du
Ŝ
ych n
n
2
s3
3,16
⋅⋅⋅⋅
s3
n
3
s4
2,15
⋅⋅⋅⋅
s4
2
n
s5
s5+3,3
1op=0,001s
