Elementi di complessità
Complessità di un algoritmo
Esempio: insertion sort
Considerazioni
Notazione asintotica
Complessità di un algoritmo
• In genere, la complessità di un algoritmo si valuta a
seconda del tempo di esecuzione e dello spazio di
memoria occupato durante la sua esecuzione.
• Tempo di esecuzione: si vuole dare una stima del
tempo necessario per eseguire l’algoritmo, dal suo inizio
fino al suo temine. Molto spesso si cerca di definire
questo a seconda della dimensione dell’input.
• Spazio di memoria : si vuole dare una stima della
memoria necessaria per eseguire l’algoritmo, dal suo
inizio fino al suo temine. Informalmente, tutte le variabili
utilizzate durante l’algoritmo contribuiscono ad
aumentare la quantità di memoria che deve essere
allocata.
Esempio di calcolo del tempo di
esecuzione
Si vuole associare ad ogni istruzione un tempo di
esecuzione dato il modello computazionale.
INSERTION-SORT(A)
1.
for j ← 2 to lenght[A]
2.
do key ← A[j]
3.
i ← j-1
4.
while (i>0) and (A[i]>key)
5.
do A[i+1] ← A[i]
6.
i← i-1
7.
A[i+1] ← key
Si vuole che il vettore A[1,…,n] sia
ordinato in ordine crescente, ossia
A[1]≤ A[2]≤ … ≤ A[n]
Ad ogni ciclo for
1
2
3
4
3
9
8 7
1
2
3
3
9
8 7
1
2
3
3
8
9 7
1
2
3
3
7
8 9
4
4
4
key
Esempio di calcolo del tempo di
esecuzione
Analisi:
INSERTION-SORT(A)
1.
for j ← 2 to lenght[A]
Costo
c1
2.
do key ← A[j]
c2
3.
i ← j-1
c3
while (i>0) and (A[i]>key)
c4
4.
Volte
eseguite
n 1
n 1
n 1
 t
 t 1
n
 j 2 t j  1
n
5.
do A[i+1] ← A[i]
c5
6.
i← i-1
c6
7.
A[i+1] ← key
c7
j 2
n
j
j 2
j
n 1
tj dipende dal numero di volte che il controllo per eseguire
ciclo while viene fatto ad ogni ciclo for (j). Si ha 1 ≤ tj ≤ i o
anche 1 ≤ tj ≤ j-1.
Esempio di calcolo del tempo di
esecuzione
Supponiamo che c1=c2=…=c7=c=1.
Possiamo calcolare il tempo complessivo dell’algoritmo:
TINS  SORT (n)  4(n  1)   j 2 t j  2 j 2 (t j  1)  2(n  1)  3 j 2 t j
n
n
n
Nel caso migliore (BEST CASE) si ha tj=1 per ogni ciclo
while.
TINS  SORT _ BEST (n)  2(n  1)  3 j 21  5(n  1)
n
Nel caso peggiore (WORST CASE) si ha tj=j per ogni ciclo
while.
TINS  SORT _ W ORST (n)  2(n  1)  3 j  2 ( j  1)  2(n  1)  3(
n
TINS SORT _WORST(n)  3 / 2n2  1 / 2n  5  O(n2 )
n(n  1)
 1)
2
Esempio di calcolo del tempo di
esecuzione
Alcune considerazioni:
• Il tempo di complessità nel caso peggiore ci dà una
garanzia del tempo massimo di esecuzione
dell’algoritmo.
• Spesso succede che il caso medio ha un
comportamento simile a quello del caso peggiore. Nel
nostro caso si ha infatti:
TINS SORT _ BEST (n)  TINS SORT _ MEDIO (n)  O(n2 )  TINS SORT _WORST(n)
• Il calcolo del tempo nel caso medio risulta spesso più
complesso del caso peggiore.
Quando un algoritmo ha una buona
complessità?
• Quando il tempo di complessità è polinomiale.
• Quando il tempo di complessità è limitata da una funzione
polinomiale.
Ecco una motivazione pratica:
n
n logn
n2
n3
2n
1 ms
1000
dati
140
dati
31
dati
10
dati
9
dati
1 sec
106
dati
62.746
dati
1000
dati
100
dati
19
dati
1 ora
3,6x 109
dati
1,6X 108
dati
60.000
dati
1532
dati
31
dati
Si suppone che in
1 ms si riesca ad
eseguire 1000
operazioni
(istruzioni).
Notazione asintotica Θ
f : N  0  R   0
c1 , c2 0  c1  c2 e n0  N  0
f (n)  ( g (n)) 
n  n0 c1 g (n)  f (n)  c2 g (n)
c2 g(n)
f(n)
c1 g(n)
f(n) cresce asintoticamente
come g(n)!
Esempio:
3 / 2n 2  7 / 2n  5  (n 2 )
n0
Notazione asintotica О
f : N  0  R   0
c 0  c e n0  N  0
f (n)  ( g (n)) 
n  n0 f (n)  cg (n)
c g(n)
f(n)
f(n) cresce asintoticamente
come non più di g(n)!
Esempio:
3 / 2n 2  7 / 2n  5  (n 2 )
7n  5  (n 2 )
n0
Notazione asintotica Ω
f : N  0  R   0
c 0  c e n0  N  0
f (n)  ( g (n)) 
n  n0 cg (n)  f (n)
f(n)
c g(n)
f(n) cresce asintoticamente
come almeno quanto g(n)!
Esempio:
3 / 2n 2  7 / 2n  5  (n 2 )
3n 2  2n  4  (n)
n0
Alcune proprietà


f (n)   ( g (n)) g (n)   (h(n))


• Proprietà transitiva

 f (n)   (h(n))

• Proprietà riflessiva

f (n)   ( f (n))

• Proprietà simmetrica
f (n)  ( g (n))  g (n)  ( f (n))
• Proprietà antisimmetrica
f (n)  ( g (n))  g (n)  ( f (n))