Cenni sulla complessità
Ilaria Castelli
[email protected]
Università degli Studi di Siena
Dipartimento di Ingegneria dell’Informazione
A.A. 2009/2010
I. Castelli
Complessità, A.A. 2009/2010
1/13
Cenni sulla complessità
Complessità di un algoritmo
Esempio: insertion sort
Considerazioni
Notazione asintotica
I. Castelli
Complessità, A.A. 2009/2010
2/13
Complessità di un algoritmo
Analisi. Si cerca di prevedere le risorse che sono richieste dall’algoritmo.
Tempo di esecuzione. Stima del tempo che l’algoritmo impiega per
risolvere il problema.
Di solito viene definito in funzione della dimensione dell’input, n.
Viene valutato in termini di numero di operazioni eseguite.
Spazio di memoria. Stima della memoria necessaria per eseguire
l’algoritmo, dal suo inizio fino al suo termine.
Tutte le variabili utilizzate durante l’esecuzione contribuiscono ad
aumentare la quantità di memoria che deve essere allocata.
I. Castelli
Complessità, A.A. 2009/2010
3/13
Complessità di un algoritmo
Analisi. Si cerca di prevedere le risorse che sono richieste dall’algoritmo.
Tempo di esecuzione. Stima del tempo che l’algoritmo impiega per
risolvere il problema.
Di solito viene definito in funzione della dimensione dell’input, n.
Viene valutato in termini di numero di operazioni eseguite.
Spazio di memoria. Stima della memoria necessaria per eseguire
l’algoritmo, dal suo inizio fino al suo termine.
Tutte le variabili utilizzate durante l’esecuzione contribuiscono ad
aumentare la quantità di memoria che deve essere allocata.
Cosa si intende per dimensione dell’input?
È lo spazio occupato dai dati relativi al problema da risolvere, o meglio, un numero
proporzionale a questo spazio.
se lavoro con un insime n è il numero di elementi
se lavoro con un grafo è il numero di nodi, o di archi, o entrambi
se lavoro con le matrici è il numero di elementi, oppure il numero di righe/colonne
...
I. Castelli
Complessità, A.A. 2009/2010
3/13
1
2
3
4
5
6
7
8
Esempio: calcolo del tempo di esecuzione
Problema: ordinamento di un vettore.
Dato il vettore A [1 . . . n] vogliamo A[1] ≤ A[2] ≤ . . . ≤ A[n]
1
INSERTION SORT (A)
for j = 2 to length [A]
key = A[ j ]
i = j − 1
w h i l e ( i >0) and (A [ i ]> k e y )
A [ i +1] = A [ i ]
i = i − 1
A [ i +1] = k e y
I. Castelli
Complessità, A.A. 2009/2010
2
3
4
3
9
8
7
3
9
8
7
3
8
9
7
3
7
8
9
4/13
1
2
3
4
5
6
7
8
Esempio: calcolo del tempo di esecuzione
Problema: ordinamento di un vettore.
Dato il vettore A [1 . . . n] vogliamo A[1] ≤ A[2] ≤ . . . ≤ A[n]
INSERTION SORT (A)
for j = 2 to length [A]
key = A[ j ]
i = j − 1
w h i l e ( i >0) and (A [ i ]> k e y )
A [ i +1] = A [ i ]
i = i − 1
A [ i +1] = k e y
/∗
/∗
/∗
/∗
/∗
/∗
/∗
c1
c2
c3
c4
c5
c6
c7
∗/
∗/
∗/
∗/
∗/
∗/
∗/
Costo
c1
c2
c3
c4
c5
c6
c7
Esecuzioni
n−1
n−1
n−1
Pn
t
Pn j=2 j
(t
− 1)
j
Pj=2
n
(t
− 1)
j
j=2
n−1
tj = numero di volte che viene eseguito il controllo per eseguire il ciclo
while, per ogni valore di j. Si ha 1 ≤ tj ≤ j.
I. Castelli
Complessità, A.A. 2009/2010
5/13
Supponiamo c1 = c2 = c3 = . . . = c7 = c = 1.
Il tempo complessivo necessario per l’esecuzione dell’algoritmo è:
TIN S−SORT (n)
=
4(n − 1) +
n
X
tj + 2
j=2
=
2(n − 1) + 3
n
X
n
X
(tj − 1)
j=2
tj
j=2
1
Best case. Si ha tj = 1 per ogni ciclo while.
TIN S−SORT −BEST (n) = 2(n − 1) + 3
n
X
1 = 5(n − 1)
j=2
2
Worst case. Si ha tj = j per ogni ciclo while.
„
TIN S−SORT −W ORST (n) = 2(n − 1) + 3
I. Castelli
Complessità, A.A. 2009/2010
«
n(n + 1)
−1
2
6/13
Considerazioni
Il caso pessimo si ha in corrispondenza di quella particolare occorrenza
iniziale dei dati per cui l’algortimo ha il peggior comportamento possibile.
Il tempo di calcolo nel caso peggiore fornisce un limite superiore al
tempo di calcolo per qualsiasi input.
Spesso nel caso medio l’algoritmo ha un comportamento simile a
quello nel caso peggiore.
Per alcuni algoritmi il caso peggiore si presenta frequentemente.
Effettuare un’analisi per il caso medio può essere più difficile rispetto
al caso peggiore.
I. Castelli
Complessità, A.A. 2009/2010
7/13
Considerazioni
Il caso pessimo si ha in corrispondenza di quella particolare occorrenza
iniziale dei dati per cui l’algortimo ha il peggior comportamento possibile.
Il tempo di calcolo nel caso peggiore fornisce un limite superiore al
tempo di calcolo per qualsiasi input.
Spesso nel caso medio l’algoritmo ha un comportamento simile a
quello nel caso peggiore.
Per alcuni algoritmi il caso peggiore si presenta frequentemente.
Effettuare un’analisi per il caso medio può essere più difficile rispetto
al caso peggiore.
Tornando al nostro esempio . . . Nel caso migliore la complessità temporale
assume la forma an + b. Nel caso peggiore an2 + bn + c.
I. Castelli
Complessità, A.A. 2009/2010
7/13
Considerazioni
Il caso pessimo si ha in corrispondenza di quella particolare occorrenza
iniziale dei dati per cui l’algortimo ha il peggior comportamento possibile.
Il tempo di calcolo nel caso peggiore fornisce un limite superiore al
tempo di calcolo per qualsiasi input.
Spesso nel caso medio l’algoritmo ha un comportamento simile a
quello nel caso peggiore.
Per alcuni algoritmi il caso peggiore si presenta frequentemente.
Effettuare un’analisi per il caso medio può essere più difficile rispetto
al caso peggiore.
Tornando al nostro esempio . . . Nel caso migliore la complessità temporale
assume la forma an + b. Nel caso peggiore an2 + bn + c.
Ci interessa l’ordine di crescita della complessità, quindi teniamo conto
solo del termine di ordine maggiore. Gli altri termini saranno trascurabili,
se n è grande. Studiamo il comportamento asintotico dell’algoritmo.
I. Castelli
Complessità, A.A. 2009/2010
7/13
Complessità asintotica
Perchè valutare la complessità per n → ∞?
gli algoritmi sono definiti per n generico
per valori piccoli di n due algoritmi possono avere efficienza
confrontabile
al crescere di n l’algortmo più veloce è quello che ha il termine
massimo di grado più basso
Tra due algoritmi che risolvono lo stesso problema è da preferire quello con
complessità asintotica inferiore.
I. Castelli
Complessità, A.A. 2009/2010
8/13
Complessità asintotica
Perchè valutare la complessità per n → ∞?
gli algoritmi sono definiti per n generico
per valori piccoli di n due algoritmi possono avere efficienza
confrontabile
al crescere di n l’algortmo più veloce è quello che ha il termine
massimo di grado più basso
Tra due algoritmi che risolvono lo stesso problema è da preferire quello con
complessità asintotica inferiore.
Ma. . . attenzione!
Per valori limitati di n un algoritmo con complessità superiore può essere
più efficiente!
I. Castelli
Complessità, A.A. 2009/2010
8/13
Complessità asintotica
Perchè valutare la complessità per n → ∞?
gli algoritmi sono definiti per n generico
per valori piccoli di n due algoritmi possono avere efficienza
confrontabile
al crescere di n l’algortmo più veloce è quello che ha il termine
massimo di grado più basso
Tra due algoritmi che risolvono lo stesso problema è da preferire quello con
complessità asintotica inferiore.
Ma. . . attenzione!
Per valori limitati di n un algoritmo con complessità superiore può essere
più efficiente!
Esempio: A1 ha complessità 100n, A2 ha complessità 3n2 . A1 è “migliore” di
A2 . Ma se n ≤ 33 è A2 il più veloce!
I. Castelli
Complessità, A.A. 2009/2010
8/13
Quando un algoritmo ha una buona complessità?
Il tempo di calcolo ha complessità polinomiale.
Il tempo di calcolo ha una complessità che è limitata da una
funzione polinomiale.
Un esempio pratico. Supponiamo che in un secondo si eseguano
1.000.000 di operazioni. Dati 4 algoritmi con complessità rispettivamente
n log n, n, n2 , e 2n , quanto tempo impieghiamo ad eseguirli?
n = 10
n = 104
n = 106
I. Castelli
n log n
3.01 op
3 ∗ 10−6 sec
133.88 op
0.133 sec
19.9 ∗ 106 op
19.9 sec
n
10 op
10−5 sec
104 op
0.01 sec
106 op
1 sec
n2
100 op
10−4 sec
108 op
100 sec
1012 op
106 sec
Complessità, A.A. 2009/2010
2n
1.024 op
10−3 sec
2 ∗ 103010 op
2 ∗ 103004 sec
9.9301029 op
9.9301023 sec
9/13
Notazione asintotica Θ
Data una funzione g(n),
Θ(g(n)) = {f (n) : ∃c1 , c2 , 0 < c1 ≤ c2 , e n0 ∈ N, tali che
0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n), ∀n ≥ n0 }
f (n) cresce asintoticamente
come g(n)
f : N → R+
Esempio:
3 2
n
2
I. Castelli
Complessità, A.A. 2009/2010
+ 72 n − 5 ∈ Θ(n2 )
10/13
Notazione asintotica O
Data una funzione g(n),
O(g(n)) = {f (n) : ∃c, c > 0, e n0 ∈ N, tali che
0 ≤ f (n) ≤ cg(n), ∀n ≥ n0 }
f (n) cresce asintoticamente
non più di g(n)
f : N → R+
Esempio:
3 2
n
2
+ 72 n − 5 ∈ O(n2 )
7n − 5 ∈ O(n2 )
I. Castelli
Complessità, A.A. 2009/2010
11/13
Notazione asintotica Ω
Data una funzione g(n),
Ω(g(n)) = {f (n) : ∃c, c > 0, e n0 ∈ N, tali che
cg(n) ≤ f (n), ∀n ≥ n0 }
f (n) cresce asintoticamente
almeno quanto g(n)
f : N → R+
Esempio:
3 2
n
2
2
+ 72 n − 5 ∈ Ω(n2 )
3n + 2n − 4 ∈ Ω(n)
I. Castelli
Complessità, A.A. 2009/2010
12/13
Alcune proprietà
Transitiva.
I
I
I
f (n) ∈ Θ(g(n)), g(n) ∈ Θ(h(n)) ⇒ f (n) ∈ Θ(h(n))
f (n) ∈ O(g(n)), g(n) ∈ O(h(n)) ⇒ f (n) ∈ O(h(n))
f (n) ∈ Ω(g(n)), g(n) ∈ Ω(h(n)) ⇒ f (n) ∈ Ω(h(n))
Riflessiva.
I
I
I
f (n) ∈ Θ(f (n))
f (n) ∈ O(f (n))
f (n) ∈ Ω(f (n))
Simmetrica.
I
f (n) ∈ Θ(g(n)) ⇔ g(n) ∈ Θ(f (n))
Antisimmetrica.
I
I. Castelli
f (n) ∈ O(g(n)) ⇔ g(n) ∈ Ω(f (n))
Complessità, A.A. 2009/2010
13/13