Asd 02 Analisi Della Complessita

30
Prof. Pier Luca Lanzi Algoritmi e Strutture Dati Analisi della complessità

description

Corso di Algoritmi e Strutture Dati 2008/2009Politecnico di Milano Prof. Pier Luca Lanzi

Transcript of Asd 02 Analisi Della Complessita

Page 1: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Algoritmi e Strutture DatiAnalisi della complessità

Page 2: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Riferimenti

Questo materiale è tratto dalle trasparenzedel corso Introduction to Algorithms (2005-fall-6046) tenuto dal Prof. Leisersonall’MIT (http://people.csail.mit.edu/cel/)

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, Second Edition, The MIT Press, Cambridge, Massachusetts London, EnglandMcGraw-Hill Book Company

Queste trasparenze sono disponibili sui sitihttp://webspace.elet.polimi.it/lanzihttp://www.slideshare.net/pierluca.lanzi

2

Page 3: Asd 02 Analisi Della Complessita

Nella lezione precedente...

Page 4: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Algoritmi, struttura dati e

analisi (asintotica) della performance

Notazione O, Ω, e Θ

Come calcolare T(n)?

Analiticamente o sviluppando l’equazione

In questa lezione vediamo altri tre metodi:

Sostituzione, Alberi, & Master Method

Page 5: Asd 02 Analisi Della Complessita

Metodo per sostituzione

Page 6: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Forse il metodo più generale,

si può applicare sempre

Analisi di Algoritmi Ricorsivi:Metodo per Sostituzione

1. “Indovinare” la forma della soluzione

2. Verificare la soluzione per induzione

3. Calcolare eventuali costanti

Page 7: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esempio

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

Assumiamo che T(1) = Θ(1)

Ipotizziamo ad esempio che T(n) sia O(n3)

Assumendo che T(k) ≤ ck3 for k < n, dimostramo per induzione che T(n)≤cn3

Soluzione

vero per (c/2)n3 – n≥0, for example, if c ≥ 2 and n ≥ 1.

7

3

33

3

3

2

2

24

24

cn

)nn)/c((cn

nn)/c(

n)/n(c

n)/n(T)n(T

bound desiderato (- residuo)

Page 8: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esempio (condizioni iniziali)

Infine dobbiamo considerare le condizioni inizialiche sono alla base della dimostrazione per induzione

In questo caso, T(1) = Θ(1) per n<n0, per un opportuno n0

Per 1≤n<n0, abbiamo “Θ(1) ” ≤cn3, se c è scelto opportunamente grande

L2.8

Questo vincolo non è stretto

Page 9: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esiste un Limite Superiore più Stretto?

Proviamo a dimostrare che T(n) è O(n2)

Assumiamo T(n) ≤ ck2 per k<n, dimostriamolo per n

È però possibile migliorare il limite dimostrando cheT(n) ≤ c1n

2 – c2n

9

)n(O

ncn

n)/n(c

n)/n(T)n(T

2

2

224

24

2

2

cn

)n(cn bound desiderato (- residuo)

Falso! Per nessuna scelta di c può essere ≤ cn2

Page 10: Asd 02 Analisi Della Complessita

Alberi di ricorsione

Page 11: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Alberi di Ricorsione

Calcoliamo la complessità andando a sviluppare l’esecuzione su una struttura ad albero

Considerato inaffidabile, è però molto intuitivo

Page 12: Asd 02 Analisi Della Complessita

Prof. Pier Luca LanziL2.12

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

Page 13: Asd 02 Analisi Della Complessita

Prof. Pier Luca LanziL2.13

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

T(n)

Page 14: Asd 02 Analisi Della Complessita

Prof. Pier Luca LanziL2.14

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

T(n/4) T(n/2)

n2

Page 15: Asd 02 Analisi Della Complessita

Prof. Pier Luca LanziL2.15

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

n2

(n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4)

Page 16: Asd 02 Analisi Della Complessita

Prof. Pier Luca LanziL2.16

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

n2

(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

Θ(1)

Page 17: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

n2

(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

Θ(1)

Perchè si chiama “albero”?

Page 18: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esempio

Calcoliamo T(n) = T(n/4) + T(n/2) + n2:

n2

(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

Θ(1)

2

16

5n

2n

2

256

25n

n 3

1652

165

1652 1

Totale =

= Θ(n2)

(serie geometrica)

Page 19: Asd 02 Analisi Della Complessita

Master method

Page 20: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Analisi di Algoritmi Ricorsivi: Master Method

Si applica a forme ricorsive del tipo,

T(n) = aT(n/b) + f(n)

dove a≥1, b>1, ed f è asintoticamente positiva

Si confronta f(n) con nlogba

Tre casi possibili

f(n) cresce più lentamente di nlogba

f(n) cresce in maniera simile a nlogba

f(n) cresce più velocemente di nlogba

20

Page 21: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Analisi di Algoritmi Ricorsivi: Master Method

Caso 1: f(n) cresce più lentamente di nlogba

f (n) = O(nlogba – ) per una costante ε > 0

Soluzione: T(n) = Θ(nlogba)

Caso 2: f(n) cresce in maniera simile a nlogba

f (n) = Q(nlogba lgkn) per una costante k≥0

Soluzione: T(n) = (nlogba lgk+1n)

Caso 3: f(n) cresce più velocemente di nlogba

f (n) = Ω(nlogba+ ) per una costante ε>0

f (n) cresce più velocemente di nlogba (di un fattore nε),ed f (n) soddisfa la condizione af (n/b)≤cf(n) per unacostante c < 1

Soluzione: T(n) = Θ(f(n))

21

Page 22: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esempi

Esempio 1: T(n) = 4T(n/2) + n

a = 4, b = 2 nlogba = n2; f(n) = n

T(n) = Θ(n2)

Esempio 2: T(n) = 4T(n/2) + n2

a = 4, b = 2 nlogba = n2; f(n) = n2

f (n) = Θ(n2lg0n), ovvero, k = 0

T(n) = Θ(n2lg n)

Esempio 3: T(n) = 4T(n/2) + n3

a = 4, b = 2 nlogba = n2; f(n) = n3

f (n) = Ω(n2+ε) con ε = 1

T(n) = Θ(n3)

23

Page 23: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Esempi

Esempio 4: T(n) = 4T(n/2) + n/lgn

a = 4, b = 2 nlogba = n2; f(n) = n/lgn

Il master method non si applica

24

Page 24: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

f (n/b)

Qual è l’Idea del Master Method?

f (n/b) f (n/b)

T (1)

Albero di ricorsione

f (n)

a

f (n/b2)f (n/b2) f (n/b2)…

a

f(n)

af(n/b)

a2f(n/b2)

h = logbn

#nodi = ah

= alogbn

= nlogba

T(1)nlogba

Page 25: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Caso 1: La performance è dominatadal costo dei nodi finali

f (n/b)

Master Method: Caso 1

f (n/b) f (n/b)

T (1)

Albero di ricorsione

f (n)

a

f (n/b2)f (n/b2) f (n/b2)…

a

f(n)

af(n/b)

a2f(n/b2)

h = logbn

T(1)nlogba

Θ(nlogba)

Page 26: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Caso 2: (k = 0) il costo è distribuito uniformemente su tuttii logbn livelli

f (n/b)

Master Method: Caso 2

f (n/b) f (n/b)

T (1)

Albero di ricorsione

f (n)

a

f (n/b2)f (n/b2) f (n/b2)…

a

f(n)

af(n/b)

a2f(n/b2)

h = logbn

T(1)nlogba

Θ(nlogbalgn)

Page 27: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Caso 3: Il costo decrescegeometricamente dalla radice allefoglie. Il costo e’ dominato dal costof(n) della radice.

f (n/b)

Master Method: Caso 3

f (n/b) f (n/b)

T (1)

Albero di ricorsione

f (n)

a

f (n/b2)f (n/b2) f (n/b2)…

a

f(n)

af(n/b)

a2f(n/b2)

h = logbn

T(1)nlogba

Θ(f(n))

Page 28: Asd 02 Analisi Della Complessita

Sommario

Page 29: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Sommario

Due metodi per risolvere

Sostituzione

Master method

Sostituzione

Intuizione

Dimostrazione per induzione

Generale, sempre applicabile

Master method

Applicabile a forme ricorsive del tipoT(n) = aT(n/b) + f(n) con a≥1, b>1, ed f asintoticamente positiva

Diretto, ma limitato a questo tipo di equazioni

30

Page 30: Asd 02 Analisi Della Complessita

Prof. Pier Luca Lanzi

Appendice: Serie Geometriche

x

xx1

11 2 for |x| < 1

x

xxxx

nn

1

11

12 per x≠1