AlgoMooc 05.02. La grande O

transcript

http://codemooc.org/algoritmi/

Algo 05.02

La grande «O»

alessandro bogliolo

Algo 05.02

alessandro.bogliolo@uniurb.itIn t

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

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

Algo 05.02

alessandro.bogliolo@uniurb.itIn p

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

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

Algo 05.02

alessandro.bogliolo@uniurb.itCo

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

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

Algo 05.02

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

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

Algo 05.02

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

Algo 05.02

s’è

quantità

valore

dimensione

Algo 05.02

alessandro.bogliolo@uniurb.itPer

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

Passo elementare: addizione ad una sola cifra

Algo 05.02

Passo elementare: addizione

Algo 05.02

Passo elementare: addizione e moltiplicazione

Algo 05.02

alessandro.bogliolo@uniurb.itO g

𝑓 𝑛

𝑔 𝑛𝑓 𝑛 = 𝑂(𝑔 𝑛 )

Algo 05.02

𝑓 𝑛

𝑔 𝑛

ℎ 𝑛

𝑓 𝑛 = 𝑂(𝑔 𝑛 )

𝑓 𝑛 = Ω(ℎ 𝑛 )

Algo 05.02

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

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

Algo 05.02

alessandro.bogliolo@uniurb.itOp

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

Algo 05.02

alessandro.bogliolo@uniurb.itCas

AlgoMooc 05.02. La grande O

Education