Algoritmi e Strutture Dati Capitolo 2 Modelli di calcolo e metodologie di analisi.

Algoritmi e Strutture Dati

Capitolo 2Modelli di calcolo e

metodologie di analisi

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl2

Modello di calcolo• L’analisi della complessità di un algoritmo è basata sul concetto

di passo elementare• Bisogna stabilire un modello di calcolo di riferimento su cui è

eseguito l’algoritmo• Macchina a registri (RAM: random access machine)

– un programma finito– un nastro di ingresso e uno di uscita– una memoria strutturata come un array

• ogni cella può contenere un qualunque valore intero/reale

• la RAM è un’astrazione dell’architettura di von Neumann



Criterio di costo uniforme

• Complessità temporale misurata come numero di passi elementari eseguiti

• Complessità spaziale misurata come numero massimo di celle di memoria occupate durante l’esecuzione

• Passi elementari:– istruzione ingresso/uscita (lettura o stampa)– operazione aritmetico/logica– accesso/modifica del contenuto della memoria

• Complessità temporale e spaziale espresse in notazione asintotica



Algoritmo fibonacci5

• Il tempo di esecuzione è O(n)– O(n) linee di codice eseguite– O(n) passi elementari eseguiti


Criterio di costo logaritmico• Il costo di una operazione dipende dalla

dimensione degli operandi dell’istruzione

• Una operazione su un operando di valore x ha costo log x

• È un criterio di costo che modella meglio il la complessità di algoritmi “numerici”

• useremo il criterio di costo uniforme(la natura dei problemi che studieremo lo consente)




Notazione asintotica



• f(n) = tempo di esecuzione / occupazione di memoria di un algoritmo su input di dimensione n

• La notazione asintotica è un’astrazione utile per descrivere l’ordine di grandezza di f(n) ignorando alcuni dettagli, come costanti moltiplicative e termini di ordine inferiore




f(n) = O( g(n) ) se due costanti c>0 e n0≥0 tali che 0f(n) ≤ c g(n) per ogni n ≥ n0

Notazione asintotica O

cg(n)

f(n)

n0 n

f(n) = ( g(n) )



Esempi:

Sia f(n) = 2n2 + 3n, allora

• f(n)=O(n3) (c=1, n0=3)

• f(n)=O(n2) (c=3, n0=3)

• f(n) O(n)



Notazione asintotica O

• La scrittura:2n2+4=O(n3)

• è un abuso di notazine per:2n2+4 O(n3)

O( g(n) )={f(n) | c>0 e n0≥0 tali che

0 f(n) ≤ c g(n) per ogni n ≥ n0}



Notare:

ngOnf 0ngnf

limn

0ngnf

lim ngOnf n

esiste) (se ngnf

lim ngOnf n



f(n) = ( g(n) ) se due costanti c>0 e n0≥0 tali che f(n) ≥ c g(n) ≥ 0 per ogni n ≥ n0


n0 n

f(n) = ( g(n) )f(n)

c g(n)



Esempi:

Sia f(n) = 2n2 – 3n, allora

• f(n)= (n) (c=1, n0=2)

• f(n)=(n2) (c=1, n0=3)

• f(n) (n3)




• La scrittura:2n2+4= (n)

• è un abuso di notazine per:2n2+4 (n)

(g(n))={f(n) | c>0 e n0≥0 tali che

0 c g(n) ≤ f(n) per ogni n ≥ n0}


Notare:

ngnf ngnf

limn

ngnf

lim ngnf n

0 esiste) (se ngnf

lim ngnf n



f(n) = ( g(n) ) se tre costanti c1,c2>0 e n0≥0 tali che c1 g(n) ≤ f(n) ≤ c2 g(n) per ogni n ≥ n0


n0 n

f(n) = ( g(n) )f(n)

c1 g(n)

c2 g(n)



Esempi:

Sia f(n) = 2n2 – 3n, allora

• f(n)= (n2) (c1=1, c2=2, n0=3)

• f(n) (n)

• f(n) (n3)




• La scrittura:2n2+4= (n2)

• è un abuso di notazine per:2n2+4 (n2)

(g(n))={f(n) | c1,c2>0 e n0≥0 tali che

c1 g(n) ≤ f(n) c2 f(n) per ogni n≥n0}


Notare che:

ngOnf g(n) nf

ngΘnf g(n)O nf

ngnf g(n) nf

ngnf g(n) nf

ngOnf e ngΩnf g(n) nf


Notazione o

Data una funzione g(n): N R, si denota con o(g(n)) l’ insieme delle funzioni f(n): N R:

o(g(n)) = {f(n) : c > 0, n0 tale che n n0 0 f(n) < c g(n) }

Notare:

0ngnf

lim ngonf n

ngO ngo


Notazione

Data una funzione g(n): N R, si denota con (g(n)) l’ insieme delle funzioni f(n):

(g(n)) = {f(n) : c > 0, n0 tale che n n0 0 c g(n) < f(n) }

Notare:

ngnf

lim ngnf n

ng ng


Riassumendo ……

menteasintotica cngnf

c0 ngΘnf 21

menteasintotica ngnf

c0 ngnf 1

menteasintotica cngnf

ngOnf 2

0 ngnf

lim ngonf n

ngnf

lim ngnf n



Analogie

O

>


Proprietà della notazione asintotica

Transitività

Riflessività

Simmetria

Simmetria trasposta

nhnf nhng e ngnf nhOnf nhOng e ngOnf nhnf nhng e ngnf

nhnf nhng e ngnf ooo

nhnf nhng e ngnf

nfnf

nfΟnf nfnf

nfng ngnf

nfng ngOnf

nfng ngonf

Un insieme in una formula rappresenta un’anonima funzione dell’insieme.

Ancora una convenzione

f(n)=n3 + O(n2)

Esempio 1:

sta per: c’è una funzione h(n) O(n2) tale che

f(n)=n3 + h(n)

n2 + O(n) = O(n2)

Esempio 2:

sta per: per ogni funzione f(n)O(n), c’è una funzione h(n) O(n2) tale che

n2 +f(n)= h(n)

lim f(n)/g(n)= c >0

f(n)=(g(n))

c/2 < f(n)/g(n) < 2c

nSe

allora

Infatti:

per n suff. grande

Se T(n) = ad nd + ad-1 nd-1 + … + a0 è un polinomio di grado d (con ad>0), allora T(n) = (nd)

Infatti:

T(n) / nd = ad + ad-1 n-1 + … + a0 n-d

che tende a ad quando n :

Esempio:


Logaritmi ……

Esponenziali ……

Polinomi ……

Fattoriali ……

P(n) = ad nd + ad-1 nd-1 + … + a0

ad > 0

f(n) = an

a >1

P(n) = (nd)P(n) = O(nd)P(n) = (nd)

an = (nd)an = (nd)

f(n) = logb(n) b>1

0,,0 dc

d

cb

n nnlog

lim

[logb(n)]c = o(nd)[logb(n)]c = O(nd)

f(n) = n! = n*(n-1)*……*2*1 n! = o(nn) n! = (an)

d

n

n na

lim



Metodi di analisi



• Misureremo le risorse di calcolo usate da un algoritmo ( tempo di esecuzione / occupazione di memoria ) in funzione della dimensione n delle istanze

• Istanze diverse, a parità di dimensione, potrebbero però richiedere risorse diverse

• Distinguiamo quindi ulteriormente tra analisi nel caso peggiore, migliore e medio

Caso peggiore, migliore e medio



• Sia tempo(I) il tempo di esecuzione di un algoritmo sull’istanza I

Tworst(n) = max istanze I di dimensione n {tempo(I)}

• Intuitivamente, Tworst(n) è il tempo di esecuzione sulle istanze di ingresso che comportano più lavoro per l’algoritmo

• Rappresenta una garanzia sul tempo di esecuzione di ogni istanza

Caso peggiore



• Sia tempo(I) il tempo di esecuzione di un algoritmo sull’istanza I

Tbest(n) = min istanze I di dimensione n {tempo(I)}

• Intuitivamente, Tbest(n) è il tempo di esecuzione sulle istanze di ingresso che comportano meno lavoro per l’algoritmo

• significa davvero qualcosa? (mah…)

Caso migliore



• Sia P(I) la probabilità di occorrenza del-l’istanza I

Tavg(n) = ∑ istanze I di dimensione n {P(I) tempo(I) }

• Intuitivamente, Tavg(n) è il tempo di esecuzione nel caso medio, ovvero sulle istanze di ingresso “tipiche” per il problema

• Richiede di conoscere/assumere una distribuzione di probabilità sulle istanze

Caso medio



Ricerca di un elemento x in un array/lista L non ordinata

Esempio 1

Tbest(n) = 1 x è in prima posizione

Tworst(n) = n x L oppure è in ultima posizione

Tavg(n) = (n+1)/2 assumendo che x L e che si trovi

con la stessa probabilità in una qualsiasi posizione

algoritmo RicercaSequenziale(array L, elem x) -> booleano1.n = lunghezza di L2.i=13.for i=1 to n do4. if (L[i]=x) then return true \\trovato5.return false \\non trovato



Ricerca di un elemento x in un array L ordinato

Esempio 2 (1/2)

Confronta x con l’elemento centrale di L e prosegue nella metà sinistra o destra in base all’esito del confronto

L[m] > x



Esempi su un array di 9 elementi

Cerca 2

Cerca 1

Cerca 9

Cerca 3

3<4 quindi a e b si invertono



Esempio 2 (2/2)

Tbest(n) = 1 l’elemento centrale è uguale a x

Tworst(n) = log n x L oppure viene trovato all’ultimo confronto

Tavg(n) = log n -1+1/n assumendo che le istanze siano equidistribuite

Poiché la dimensione del sotto-array su cui si procede si dimezza dopo ogni confronto, dopo l’i-esimo confronto il sottoarray di interesse ha dimensione n/2i

Risulta n/2i = 1 per i=log2n



Delimitazioni

inferiori e superiori



Delimitazioni superiori (upper bound)DefinizioneUn algoritmo A ha costo di esecuzione O(f(n)) su istanze di dimensione n e rispetto ad una certa risorsa di calcolo, se la quantità r di risorsa sufficiente per eseguire A su una qualunqueistanza di dimensione n verifica la relazione r(n)=O(f(n))

DefinizioneUn problema P ha una complessità O(f(n)) rispetto ad una risorsa di calcolo se esiste un algoritmo che risolve P il cui costo di esecuzione rispetto quella risorsa è O(f(n))



Delimitazioni inferiori (lower bound)DefinizioneUn algoritmo A ha costo di esecuzione (f(n)) su istanze di dimensione n e rispetto ad una certa risorsa di calcolo, se la massima quantità r di risorsa necessaria per eseguire A su istanze di dimensione n verifica la relazione r(n)= (f(n))

DefinizioneUn problema P ha una complessità (f(n)) rispetto ad una risorsa di calcolo se ogni algoritmo che risolve P hacosto di esecuzione (f(n)) rispetto quella risorsa



Ottimalità di un algoritmo

DefinizioneDato un problema P con complessità (f(n)) rispetto ad una risorsa di calcolo, un algoritmo che risolve P è ottimo se ha costo di esecuzione O(f(n)) rispetto quella risorsa



Analisi di algoritmi ricorsivi



L’algoritmo di ricerca binaria può essere scritto come algoritmo ricorsivo.

Esempio

Come analizzarlo?

algoritmo RicercaBinariaRic(array L, elem x, int i, int j) -> booleano1.if (i>j) then return non trovato2.m= (i+j)/23.if (L[m]=x) then return trovato4.if (L[m]>x) then return RicercaBinariaRic(L, x, i, m-1)5. else return RicercaBinariaRic(L, x, m+1,j)

gli indici i e j indicano la porzione di L in cui cercare l’elemento x



Il tempo di esecuzione può essere descritto tramite una equazione di ricorrenza:

Equazioni di ricorrenza

c + T(n/2) se n>1

1 se n=1T(n) =

Vari metodi per risolvere equazioni di ricorrenza: iterazione, sostituzione, teorema Master...



Idea: “srotolare” la ricorsione, ottenendo una sommatoria dipendente solo dalla dimensione n del problema iniziale

Metodo dell’iterazione

Esempio: T(n) = c + T(n/2) T(n/2) = c + T(n/4) ...

T(n) = c + T(n/2) = 2c + T(n/4) = = ( ∑j=1...i c ) + T(n/2i) = i c + T(n/2i)

Per i=log2n: T(n) = c log n + T(1) = O(log n)



Esercizi

Risolvere usando il metodo dell’iterazione le seguenti equazioni di ricorrenza:

• T(n)= n + T(n-1), T(1)=1;

• T(n)= 9 T(n/3) + n(soluzione sul libro di testo: Esempio 2.4)



Idea:

1. indovinare la (forma della) soluzione

2. usare induzione matematica per provare che la soluzione è quella intuita

3. risolvi rispetto alle costanti

Metodo della sostituzione



Metodo della sostituzione

Esempio: T(n) = n + T(n/2), T(1)=1Assumiamo che la soluzione sia T(n) ≤ c n per una costante c opportuna

Passo base: T(1)=1≤ c 1 per ogni c1

Passo induttivo: T(n)= n + T(n/2) ≤ n+c (n/2) = (c/2+1) n Quindi T(n) ≤ c n per c≥2



Teorema Master

Permette di analizzare algoritmi basati sulla tecnica del divide et impera:- dividi il problema (di dimensione n) in a sottoproblemi di dimensione n/b- risolvi i sottoproblemi ricorsivamente- ricombina le soluzioni

Sia f(n) il tempo per dividere e ricombinare istanze di dimensione n. La relazione di ricorrenza è data da:

a T(n/b) + f(n) se n>1

1 se n=1T(n) =



Algoritmo fibonacci6

a=1, b=2, f(n)=O(1)



Teorema Master

n vs f(n)logba

quale va più velocemente a infinito?

Stesso ordine asintotico T(n) = (f(n) log n)

Se una delle due è “polinomialmente” più veloce T(n) ha l’ordine asintotico della più veloce



La relazione di ricorrenza:

Teorema Master

ha soluzione:

a T(n/b) + f(n) se n>1

1 se n=1T(n) =

1. T(n) = (n ) se f(n)=O(n ) per >0logba logba -

2. T(n) = (n log n) se f(n) = (n )logba logba

3. T(n) = (f(n)) se f(n)=(n ) per >0 e a f(n/b)≤ c f(n) per c<1 e n sufficientemente grande

logba +



1) T(n) = n + 2T(n/2) a=2, b=2, f(n)=n=(n ) T(n)=(n log n) (caso 2 del teorema master)

Esempi

log22

2) T(n) = c + 3T(n/9) a=3, b=9, f(n)=c=(n ) T(n)=(√n) (caso 1 del teorema master)

log93 -

3) T(n) = n + 3T(n/9) a=3, b=9, f(n)=n=(n ) (caso 3 del teorema master)

log93 +

T(n)=(n)3(n/9)≤ c n per c=1/3



4) T(n) = n log n + 2T(n/2) a=2, b=2, f(n) =(n ) ma f(n)(n ), > 0

Esempi

log22

log22+

non si può applicareil teorema Master!



Esempio: T(n) = T(n) + O(1), T(1) = 1

Cambiamento di variabile

T(n) = T(n1/2) + O(1)

n=2x x =log2 n

T(2x) = T(2x/2) + O(1) R(x):=T(2x)

R(x) = R(x/2) + O(1) R(x) = O(log x)

T(n) = O(log log n)



Idea: – disegnare l’albero delle chiamate ricorsive indicando la dimensione di ogni

nodo– studiare il tempo speso per tutte le chiamate di un dato livello dell’albero– studiare il numero di livelli dell’albero

Esempio 1: T(n) = T(n/3) + T(2n/3) + n, T(1) = 1

Un’altra tecnica utile:

Analisi dell’albero della ricorsione

Esempio 2: T(n) = 2 T(n-1) + 1, T(1) = 1



Esercizio

Progettare una versione ricorsiva dell’algoritmo di ricerca sequenziale, si fornisca l’equazione di ricorrenza che descrive lasua complessità temporale e la si risolva con una delle tecniche studiate.



SoluzioneRicercaSeq (A, x)

1. return RicercaSeqRic(A,x,1)

RicercaSeqRic(A, x, i)

1. if i > n then return non trovato

2. if A[i] = x then return trovato

else return RicercaSeqRic(A,x,i+1)

Complessità temporale dell’algoritmo:

T(n) = c + T(n-1); T(1) = O(1)

T(n) = c + T(n-1) = 2c + T(n -2)= 3c + T(n -3)= … = c(n -1) + T(1) = c(n -1) + O(1)= O(n)

usando il metodo dell’iterazione

Algoritmi e Strutture Dati Capitolo 2 Modelli di calcolo e metodologie di analisi.

Documents

Transcript of Algoritmi e Strutture Dati Capitolo 2 Modelli di calcolo e metodologie di analisi.