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.