Introduzione alla complessità
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Complessità
analisi degli algoritmi in termini di indici di qualitá
algoritmo “migliore”
indici:
occupazione di memoria
tempo di esecuzione
f (n)
calcolo del valore dell’indice in funzione della dimensione dei dati di ingresso
distribuzione dei dati in ingresso
caso peggiore
caso migliore
valore di un polinomio
dato polinomio
A m x m + A m −1 x m −1 + . . . + A 1 x + A 0 valutarlo in x 0
dimensione n = m-1
numero dei coefficienti A i
valore di un polinomio
algoritmo 1
pol ← A 0 i ← 1
while i ≤ m pot ← 1 k ← i
while k > 0
pot ← pot × x 0 k ← k - 1
pol ← A i × pot + pol i ← i+1
¯¯¯|C 0
|
¯¯¯|
| C 1 (n − 1)
|
¯¯¯|
| C 2 P n
l =1 l = C 2 n(n−1) 2
|
¯¯¯| C 3 (n − 1)
|
tempo di esecuzione
f ‘ (n) = C + C (n − 1) + C n(n − 1)
+ C (n − 1)
valore di un polinomio
algoritmo 2
regola di Horner
(. . . (A m x + A m −1 )x + A m −2 )x . . . + A 1 )x + A 0
pol ← A m i ← m-1
while i ≥ 0 do
pol ← pol × x 0 +A i i ← i-1
¯¯¯|D 0
|
¯¯¯|
| D 1 (n − 1)
|
tempo di esecuzione
f T ” (n) = D 0 + D 1 (n − 1)
algoritmo “migliore” ?
comportamento asintotico per n→ ∞
notazione O
f (n) è O(g(n))
se esistono due costanti positive c e n 0 tali che 0 ≤ f(n) ≤ cg(n)
per ogni n ≥ n 0
n
0c g(n)
n f(n)
g (n) è un limite asintotico superiore per f(n)
limite superiore di f(n) a meno di un fattore costante
limite superiore alla complessità dell’algoritmo
classi di complessità k costante
log n logaritmica
√ n
n lineare
n log n subquadratica n 2 quadratica
n 3 cubica
n a polinomiale a n esponenziale
n ! fattoriale
10 20 30 40 50 60
10 20 30 40 50 60
log(x) 2 sqrt(x) x**2 x 2**x
valore di un polinomio
f ‘ (n) = O(n 2 ) f ” = O(n)
caveat
f (n) equivalenti a meno di un fattore costante
0 500 1000 1500 2000
0 2 4 6 8 10
1000*x 10*x