AlgoMooc 05.02. La grande O
-
Upload
alessandro-bogliolo -
Category
Education
-
view
56 -
download
0
Transcript of AlgoMooc 05.02. La grande O
http://codemooc.org/algoritmi/
Algo 05.02
La grande «O»
alessandro bogliolo
Algo 05.02
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
rati
ca
𝑓 𝑛 = 2 + 𝑛 ∗ 1 + 1 𝑓 𝑛 = 2 + 𝑔(𝑛) ∗ 1 + 1
𝑓 𝑛 = 2 + 𝑛 ∗ 𝑘 + 1 𝑓 𝑛 = 2 + 𝑔(𝑛) ∗ 𝑘 + 1
Algo 05.02
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
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
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
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
ran
de
𝑓 𝑛 = 2 + 𝑛 ∗ 𝑛 ∗ (2 + 𝑛 ∗ 1 + 1)
𝑓 𝑛 = 2 + 𝑛 ∗ 𝑛 ∗ 2 + 𝑛 ∗ 1 + 1 = 2 + 3 ∗ 𝑛2 + 𝑛3 𝜖 𝑂(𝑛3)
Algo 05.02
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