http://codemooc.org/algoritmi/

Algo 05.02

La grande «O»

alessandro bogliolo

Algo 05.02

alessandro.bogliolo@uniurb.itIn t

eori

aDi cosa abbiamo bisogno per valutare la complessità di un algoritmo?

Dimensione dei dati su cui opera

Numero di passi elementari espressi in funzione di n Funzione monotona crescente

Algo 05.02

alessandro.bogliolo@uniurb.itIn p

rati

ca

𝑓 𝑛 = 5 𝑓 𝑛 = 2 + 𝑘 ∗ 1 + 1

Algo 05.02

alessandro.bogliolo@uniurb.itIn p

rati

ca

𝑓 𝑛 = 2 + 𝑛 ∗ 1 + 1 𝑓 𝑛 = 2 + 𝑔(𝑛) ∗ 1 + 1

𝑓 𝑛 = 2 + 𝑛 ∗ 𝑘 + 1 𝑓 𝑛 = 2 + 𝑔(𝑛) ∗ 𝑘 + 1

Algo 05.02

alessandro.bogliolo@uniurb.itCo

mp

osi

zio

ne

𝑓 𝑛 = 2 + 𝑛 ∗ 1 + 𝑛 ∗ 1

𝑓 𝑛 = 2 + 𝑛 ∗ 𝑘 + 𝑛 ∗ ℎ

Algo 05.02

alessandro.bogliolo@uniurb.itCo

mp

osi

zio

ne

𝑓 𝑛 = 2 + 𝑛 ∗ (𝑛 ∗ 1)

𝑓 𝑛 = 2 + 𝑛 ∗ (𝑘 + 𝑛 ∗ ℎ )

Algo 05.02

alessandro.bogliolo@uniurb.itCo

mp

osi

zio

ne

𝑓 𝑛 = 2 + 𝑛 ∗ 𝑛 ∗ (2 + 𝑛 ∗ 1 + 1)

Algo 05.02

alessandro.bogliolo@uniurb.itCo

s’è

n?

quantità

valore

dimensione

Algo 05.02

alessandro.bogliolo@uniurb.itPer

esem

pio

Passo elementare: incremento

• Contiamo fino a n• Contiamo quanti quadretti 1x1 ci sono in un quadrato di lato n• Contiamo quanti cubetti 1x1x1 ci sono in un cubo di lato n

• Calcoliamo n*n• Calcoliamo n*n*n• Calcoliamo 2n

Algo 05.02

alessandro.bogliolo@uniurb.itPer

esem

pio

Passo elementare: addizione ad una sola cifra

• Contiamo fino a n• Contiamo quanti quadretti 1x1 ci sono in un quadrato di lato n• Contiamo quanti cubetti 1x1x1 ci sono in un cubo di lato n

• Calcoliamo n*n• Calcoliamo n*n*n• Calcoliamo 2n

Algo 05.02

alessandro.bogliolo@uniurb.itPer

esem

pio

Passo elementare: addizione

• Contiamo fino a n• Contiamo quanti quadretti 1x1 ci sono in un quadrato di lato n• Contiamo quanti cubetti 1x1x1 ci sono in un cubo di lato n

• Calcoliamo n*n• Calcoliamo n*n*n• Calcoliamo 2n

Algo 05.02

alessandro.bogliolo@uniurb.itPer

esem

pio

Passo elementare: addizione e moltiplicazione

• Contiamo fino a n• Contiamo quanti quadretti 1x1 ci sono in un quadrato di lato n• Contiamo quanti cubetti 1x1x1 ci sono in un cubo di lato n

• Calcoliamo n*n• Calcoliamo n*n*n• Calcoliamo 2n

Algo 05.02

alessandro.bogliolo@uniurb.itO g

ran

de

𝑓 𝑛

𝑔 𝑛𝑓 𝑛 = 𝑂(𝑔 𝑛 )

Algo 05.02

alessandro.bogliolo@uniurb.itO g

ran

de

𝑓 𝑛

𝑔 𝑛

ℎ 𝑛

𝑓 𝑛 = 𝑂(𝑔 𝑛 )

𝑓 𝑛 = Ω(ℎ 𝑛 )

Algo 05.02

alessandro.bogliolo@uniurb.itO g

ran

de

𝑓 𝑛 = 2 + 𝑛 ∗ 𝑛 ∗ (2 + 𝑛 ∗ 1 + 1)

𝑓 𝑛 = 2 + 𝑛 ∗ 𝑛 ∗ 2 + 𝑛 ∗ 1 + 1 = 2 + 3 ∗ 𝑛2 + 𝑛3 𝜖 𝑂(𝑛3)

Algo 05.02

alessandro.bogliolo@uniurb.itOp

eraz

ion

i ele

men

tari Incremento

Addizione a una cifra

Addizione a un numero limitato di cifre

Moltiplicazione a un numero limitato di cifre

Algo 05.02

alessandro.bogliolo@uniurb.itQu

anto

so

no

gra

nd

i q

ues

te O

Algo 05.02

alessandro.bogliolo@uniurb.itCas

oo

ttim

o, m

edio

, pes

sim

o