Silvia Rossi

Lezione n.

Parole chiave:

Corso di Laurea:

Insegnamento:

Email Docente:

A.A. 2009-2010

Silvia Rossi

Cenni sulla complessità

23

Informatica

Programmazione I

srossi@na.infn.it

Costo degli algoritmi

Abbiamo visto che dato un problema esistono diversi algoritmi che lo risolvono

– E per ogni algoritmo più programmi che lo implementano (con diversi gradi di efficienza)

Come scegliere l’algoritmo (o il programma) più adatto?

Ogni programma necessita di una certa quantità di

memoria ed impiega una certa quantità di tempo per essere eseguito

Le risorse tempo e spazio di memoria sono spesso in conflitto

– aumentando la memoria occupata dal programma si può diminuire il tempo di calcolo

problema G₁ G₂

P¹_G1

P²_G1

...

...

Costo degli algoritmi

Ci occuperemo della valutazione dell’efficienza o complessità di un programma in termini del solo tempo di calcolo trascurando la quantità di memoria utilizzata e supponendo quindi che

non ci sia alcun limite alla quantità di memoria

utilizzata dal programma.

Costo degli algoritmi La complessità di un algoritmo è una stima quantitativa di

come varia il tempo di calcolo al variare della dimensione dei dati di input

Il tempo di calcolo di un programma su un particolare calcolatore dipende:

– dai dati di input

• dimensione, caratteristiche come ordinamento, compattezza, etc.

– dalla complessità delle istruzioni

– dalla quantità di memoria usata dal programma

• se è limitata o se dipende da altri programmi in esecuzione

– dalla velocità di esecuzione delle operazioni elementari:

• addizione, moltiplicazione, valutazione delle espressioni booleane, etc.

– dalla velocità di accesso alla memoria e ai dispositivi di I/O – …

Valutiamo l’efficienza di un programma solo determinando la complessità del suo algoritmo

Costo degli algoritmi

Sia I

una istruzione del programma P

:

– I_k = e_k espressione elementare

• assegnazione di costante, espressione semplice.

– I_k = E_k espressione composta

• Assegnazione di espressione, espressione composta, etc.

– I_k = B_k istruzione composta

• blocco (sequenza) di istruzioni: corpo di funzione, di cicli, etc.

– I_k = F_k costrutto di controllo

• for(), while () …, if () else () , etc.

Sia C(I_k) la funzione che associa un numero intero (tempo di calcolo) all’esecuzione di ogni istruzione del programma

funzione di costo C(I ) = n C : P à N

Costo degli algoritmi

Sia e una espressione elementare:

– singola assegnazione

con r-value costante o singola variabile

x ß 4, y ß z

– espressione semplice

3 + x Y

– espressione booleana semplice

a and b

– accesso a elemento di array A[i,…,k]

con indici costanti

matrice[3,j]

C(e) = 1

C(x ß c) = 1

C(3 + x) = 1

C(a and b) = 1

C(A[i,…,k]) = 1

Costo degli algoritmi

Sia E una espressione composta:

– assegnazione con espressione

a destra: x ß E (istruzione semplice) x ß y + 3

– accesso a elemento di array A[E₁,…,E_k] con uno o più indici di tipo espressione

tabella[4+i,j]

– composizione di espressioni:

E₁ and E_k

(x * 3) > (y / 2)

C(x ß E) = 1 + C(E)

C(A[E

,…,E

] ) = 1 + C(E

)+….+C(E

)

C(E

and E

) = C(E

)+C(E

)

Costo degli algoritmi

Sia B un blocco di istruzioni

– una sequenza di istruzioni

B = E₁,E₂,….,E_n che compongono il corpo di un ciclo,

una funzione, di un if etc.

C(B) = C(E

)+C(E

)+….+C(E

)

E₁

E_n E₂

Costo degli algoritmi

Sia F una istruzione di controllo di selezione

– F = if (E) {B}

C(F) = C(E) + C(B)

– F = if (E) {B1} else {B2 } C(F) = C(E) + max(C(B₁), C(B₂))

E?

no B

si

E?

B₁ B₂

no si

Costo degli algoritmi

Sia F una chiamata di funzione

– F = foo(x₁,…,x_n) foo(x₁,…,x_n){

B

return E_k}

C(I

) = n + C(B) + C(E

)

Costo degli algoritmi

Sia F una istruzione di controllo di iterazione

– F = for (E1;E2;E3) {B }

C(F) = C(E₁) + C(E₂) +

S ^[C(B)+C(E

)+C(E

) ]

iterazioni

for (i=n1; i<=n2; i++) {B } n2

C(F) = 2 +

S

i=n1

Solo se il costo di B non dipende da i si ha

C(F) = 2 + (n2-n1+1) ´ [C(B)+2]

Costo degli algoritmi

Sia F una istruzione di controllo di iterazione

– F = while(E) {B}

– F = do {B} while(E)

– Dove M è il massimo numero (se esiste) di iterazioni possibili:

• Se è possibile determinare il maggiorante M questo deve riferirsi al caso peggiore (è quello che interessa nello studio dell’efficienza degli algoritmi)

• ci sono casi in cui è impossibile determinare M

(è anche impossibile determinare se il ciclo termina o no)

C(F) = C(E) + M ´ [C(E)+C(B)]

C(F) = M ´ [C(E)+C(B)]

Costo degli algoritmi In altri termini non esiste alcun algoritmo in grado di determinare,

dato un qualsiasi while loop quanto vale il massimo numero di iterazioni ed in particolare non esiste un algoritmo in grado di decidere, dato un qualsiasi while loop, se questo termina

sempre in un numero finito di passi oppure no. Un tipico esempio si basa sulla:

Congettura di Collatz: partendo da un numero naturale qualsiasi a>0 e applicando la regola

= 3a_n+1 se an è dispari > 1 a_n+1

= a_n / 2 se an è pari

si raggiunge sempre il valore 1.

Costo degli algoritmi

Per esempio, iniziando con n = 6, otteniamo la sequenza:

6, 3, 10, 5, 16, 8, 4, 2, 1.

La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal

valore di partenza

La congettura risulterebbe quindi falsa se esistesse una

sequenza che non contiene l'1;

Costo degli algoritmi

La congettura di Collatz non è stata dimostrata. Pertanto non si è in grado di stabilire se la complessità della function qui sotto definita è infinita oppure no.

int function collatz(int a) WHILE (a>1) {

if (a % 2=1) a=3*a+1;

else

a= a / 2;

return a;

Costo degli algoritmi Esempio: calcoliamo la complessità dell’algoritmo della radice

quadrata:

C(B₁) = 3 (inizializzazione di Xs, eps, lettura a)

C(B₂) = 5 (assegnazioni di Xp, calcolo nuovo Xp e assegnazione Xs) C(B₃) = 1 (stampa risultato)

C = 3 + C(do {B2} while(E)) + 1 = 3 + M ´ (5 + 3) + 1 = 3 + 8M + 1

leggi(a)

eps ß 0.001 Xs ß 1

do:

Xp ß Xs

Xs ß (Xp + a/Xp) / 2 while (abs(Xs-Xp) ≥ eps) stampa (Xs)

B₁ (1 volta)

B₂ (n volte)

B₃ (1 volta)

17

Esempio

Calcoliamo il costo dell’algoritmo di Bubble-Sort.

for(k=0; k<N-1; k++) for (j=N-2; j>=k; j--)

if (vet[j] > vet[j+1]) scambia (vet[j],vet[j+1]);

Il caso peggiore dell’Bubble sort è quando il vettore iniziale ha elementi tutti diversi ed è già ordinato ma in senso decrescente.

In questo caso accade che, ad ogni iterazione k del ciclo esterno, si ha il numero massimo di scambi (n-1+k), ossia tutti le coppie sono

scambiate perché diverse e ordinate in senso inverso.

N^° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2

18

Esempio

Calcoliamo il costo dell’algoritmo di Bubble-Sort.

for(k=0; k<N-1; k++) for (j=N-2; j>=k; j--)

if (vet[j] > vet[j+1]) scambia (vet[j],vet[j+1]);

Come primo passo determiniamo il costo della funzione scambia(x,y).

Esso sarà pari a 2 più il costo del corpo della funzione che comprende tre assegnazioni; quindi

C(scambia)=9+2

Ancora, il costo della condizione relativa all’istruzione if è : C(if) = 1 + C(scambia) = 12

Tale costo è anche il costo del corpo del loop interno ed è indipendente dall’indice j.

Siccome il corpo del for interno è eseguito (N –2) - k +1 = N – k -1 volte si avrà:

C(for interno) = (N – k-1) • 12

Dunque la complessità del for interno dipende dal valore dell’indice k

19

Quindi il costo complessivo dell’algoritmo sarà dato da:

C(bubblesort) = = 12N(N-1) – 12(1+2+...+N-2)- 12(N-1)=

=12N²-12N –12(N-1)(N-2))/2 -12N-12=

= 12N²-12N-6(N²-2N-N+2)-12N-12=6N²-6N

N-2

S(12N-12k-12)

k=0

20

Esercizio

Calcolare il costo dell’algoritmo di insertion sort ed il costo dell’algoritmo di selection sort .

Verificare che anche essi hanno un costo proporzionale al quadrato del numero di elementi degli array.