ZŁOŻONOŚĆ
OBLICZENIOWA
ALGORYTMÓW
ZŁOŻONOŚĆ
OBLICZENIOWA
ALGORYTMÓW
pesymistyczna
czasowa
średnia
Złożoność
pesymistyczna
pamięciowa
średnia
DANE
Wyznacz największą spośród 3 liczb rzeczywistych.
Oblicz 2
n
, dla pewnej liczby naturalnej n.
Sprawdź czy dana liczba naturalna n jest liczbą pierwszą.
Wyznacz największy wspólny dzielnik dwóch liczb naturalnych.
D = { ( x, y, z ) : x,y,z
R } = R
R
R = R
3
D = { n : n
N } = N
D = { n : n
N } = N
D = { (a,b) : a,b
N } = N
N = N
2
Oblicz sumę płac pracowników w firmie.
Wyznacz maksimum z ciągu liczb rzeczywistych.
Oblicz iloczyn dwóch wektorów x, y o współrzędnych
rzeczywistych.
D = { ( n, p
1
, ... ,p
n
) : n
N , p
1
, ... ,p
n
R }
D = { ( n, x
1
, ... , x
n
) : n
N , x
1
, ... ,
x
n
R }
D = {( n, x
1
, ... , x
n,
y
1
, ... ,y
n
) : n
N , x
1
, ... , x
n
,
y
1
, ... ,y
n
R }
Zbiór operacji jednostkowych Pascala (J) :
operatory arytmetyczne : + - * / div mod
operatory logiczne : and or
not
operatory relacyjne : < <= > >=
= <>
nadanie wartości zmiennej typu prostego
obliczenie wartości zmiennej indeksowanej
inicjalizacja wywołania procedury lub
funkcji
przekazanie wartości parametru
aktualnego
wykonanie instrukcji pustej, wejścia lub
wyjścia
Dany jest program P w Pascalu o zbiorze danych D.
Zakładamy, że :
• P jest poprawny
• obliczenie programu P na każdej danej z D jest skończone
Definiujemy funkcję
t : D
N
następująco :
t(d) = ilość operacji ze zbioru J
występujących w obliczeniu programu P na
danej d
D
t - pełna funkcja złożoności czasowej programu P
( pełna funkcja kosztu programu P )
PEŁNA FUNKCJA ZŁOŻONOŚCI
CZASOWEJ
PRZYKŁADY
program
max2;
t(d)
var x,y : real;
Max : real;
begin
read (x,y);
2
if x > y then Max := x
2 lub 1
else Max := y
0 lub 1
writeln (Max)
1
end.
t(d)
=
5
Wyznacz maksimum z dwóch liczb rzeczywistych x, y.
D = { ( x,y ) : x,y
real }
D = { (a, b, c) : a,b,c
real } = real
3
Wyznacz pierwiastki rzeczywiste równania
kwadratowego
ax
2
+ bx + c = 0 .
program
pierwiastki;
t(d)
var a,b,c,delta, x1,x2 : real;
begin
read (a,b,c);
3
delta := b*b - 4*a*c;
5
if delta > 0 then
1
begin
delta := sqrt(delta);
2
x1 := (-b + delta) / (2*a);
5
x2 := (-b - delta) / (2*a);
5
write (x1, x2)
2
end
else if delta = 0 then
1
begin
x1 := -b/(2*a);
4
write (x1);
1
end
else write(‘Nie ma pierwiastków rzecz')
1
end.
t(d) = 23 lub t(d) = 15 lub t(d) = 11
program
silnia;
t(d)
var n : Byte ;
silnia : LongInt ;
begin
readln (n);
1
if ( n = 0) or (n = 1)
3
then silnia := 1
1
else begin
silnia := 1;
1
for i := 2 to n do
1 * (n-1)
silnia := silnia * i ;
2 * (n-1)
end;
writeln (n);
1
end.
t(n) = 1+3+1=5 dla n=0 lub n=1
t(n) = 1+3+1+(n-1)+2*(n-1)+1 = 3n + 3
dla n>1
D = { n : n
byte }
Oblicz n! dla n>= 0.
program
pierwsza
;
t(d)
var n, p : word; b : boolean;
begin
readln (n);
1
p := 2;
1
b := true;
1
while ( (p*p <= n) and b) do
3*n
begin
if n mod p = 0 then b := false;
2*(n
-1)+1
p := p + 1;
2*(n -1)
end;
if b then writeln (‘To jest liczba pierwsza’)
1 lub
2
else writeln (‘ To nie jest liczba pierwsza’);
1 lub
0
end.
t(n)
7
n
+ 1
D = { n : n
word }
Sprawdź czy liczba naturalna n, n >= 0, jest liczbą pierwszą .
n jest liczbą parzystą , tzn .: n mod 2 = 0
t(n) = 15
n jest postaci 3*k dla pewnego k N
t(n) = 22
n jest liczbą pierwszą
t(n) = 7
n
Dowolną funkcje r : D
W nazywamy rozmiarem danych
.
ROZMIAR DANYCH
Oblicz sumę płac pracowników w firmie.
D = { ( n, p
1
, ... ,p
n
) : n
N , p
1
, ... ,p
n
R }
W = { n : n
N } = N
Wyznacz maksimum z ciągu liczb rzeczywistych.
D = { ( n, x
1
, ... , x
n
) : n
N , x
1
, ... , x
n
R }
W = { n : n
N } = N
Oblicz iloczyn dwóch macierzy A
n,k
, B
k,m,
o wyrazach
rzeczywistych
D = {( n, k, m, A, B
) : n,k,m
N , A
Mac
n,k
(R), B
Mac
k,m
(R) }
W = {(n, k, m) : n,k,m
N} = N
3
lub
W = { n : n =
max {n,k,m} } = N
PESYMISTYCZNA ZŁOŻONOŚĆ CZASOWA
J
- zbiór operacji jednostkowych Pascala
(niekoniecznie wszystkich)
P
- program w Pascalu
D
- zbiór danych programu P
W
- zbiór rozmiarów danych programu P
t
- pełna funkcja złożoności czasowej programu P
Funkcję T: W - -
N
zdefiniowaną następująco
:
T(w) = sup { t(d) : d
D ^ r(d) = w }
nazywamy
pesymistyczną złożonością czasową
programu
NOTACJA "O"
Niech g : N R .
O(g) = { f : N
R : istnieją stałe : c
R, c > 0 i n
0
N
takie, że
|f(n)|
c * |g(n)|
dla wszystkich naturalnych n
n
0
}
Dane są dwie funkcje f, g : N
R .
Mówimy, że
„ funkcja f jest co najwyżej rzędu
funkcji g „
jeśli
f
O(g) .
Oznaczenie :
f(n) = O(g(n))
NOTACJA "
"
Niech g : N R .
(g) = { f : N
R : istnieją stałe : c
R, c > 0 i n
0
N , n > 0
takie, że
|f(n)|
c * |g(n)|
dla wszystkich naturalnych n
n
0
}
Dane są dwie funkcje f, g : N
R .
Mówimy, że
„ funkcja f jest co najmniej rzędu
funkcji g „
jeśli
f
O(g)
.
Oznaczenie :
f(n) =
(g(n))
NOTACJA " "
Dane są dwie funkcje f, g : N
R .
Mówimy, że
„ funkcja f jest dokładnie rzędu
funkcji g „
jeśli
f
(g)
.
Niech g : N R
(g) = O(g)
(g)
Oznaczenie :
f(n) =
(g(n))
Jeśli f = O(g) i g = O(h) , to f =O(h)
Jeśli f = O(g) i h =O(r) , to fh =
O( gr )
Jeśli f
jest wielomianem stopnia d, to f
=
O(n
d
)
Własności notacji O
Dla algorytmu
A
i zbioru operacji
J
:
znajdujemy funkcję
g : W
R
, gdzie W jest zbiorem rozmiaru
danych
i rzeczywistą stałą
c > 0
taką, że
T
A,J,W
(w)
c * |g(w)|
dla prawie wszystkich w
W,
Wtedy piszemy
T(w) = O(g(w))
( „
T jest co najwyżej
rzędu g”
)
PODSUMOWANIE
D = { ( n, p
1
, ... ,p
n
) : n
byte , p
1
, ... ,p
n
real
W = { n : n
byte}
program
suma;
const ile = 100;
var p : array [1..ile] of real;
n : byte; s : real;
begin
read (n);
1
s := 0;
1
for i := 1 to n do
n
begin
read (p[i]);
2n
s := s + p[i];
3n
end;
writeln (s)
1
end.
6n + 3 <= 7n
dla n
>2
T(n) = O(n)
program
pierwsza
;
t(d)
var n, p : word; b : boolean;
begin
readln (n);
1
p := 2;
1
b := true;
1
while ( (p*p <= n) and b) do
3*n
begin
if n mod p = 0 then b := false;
2*(n
-1)+1
p := p + 1;
2*(n -1)
end;
if b then writeln (‘To jest liczba pierwsza’)
1
else writeln (‘ To nie jest liczba pierwsza’);
1
end.
t(n)
7
n
+ 1
T(n) =
O(
n )
D = { n : n
word }
Sprawdź czy liczba naturalna n, n >= 0, jest liczbą pierwszą .
Po co złożoność ?
NA KONIEC
Dobry algorytm jest jak „ostry nóż” - robi dokładnie to, co ma
robić,
z najmniejszym wysiłkiem.
Używanie złego algorytmu to jak „krajanie steku
korkociągiem”.
Rezultat może nie być ani efektywny ani „apetyczny”.
ZAD. Posortuj tablicę zawierającą milion
liczb (10
6
) .
Komputer osobisty : wykonuje 1 milion (10
6
) operacji na
sekundę
Sortujemy algorytmem przez scalanie :
T(n) = 50nlgn
T(10
6
) = 50 * 10
6
* lg10
6
/ 10
6
1000 sekund
16.67
minut
Superkomputer : wykonuje 100 milionów (10
8
) operacji na
sekundę.
Sortujemy algorytmem przez wstawianie :
T(n) = 2n
2
T(10
6
) = 2 * (10
6
)
2
/ 10
8
= 20 000 sekund
5.56 godzin
UWAGA
: Sortowanie przez wstawianie jest szybsze
od sortowania przez scalanie
dla małych n
Komputer osobisty wykonał zadanie
20 razy szybciej.