Complessità e Notazione Asintotica
Quando si confrontano algoritmi, determinare
il tempo di esecuzione
-È complicato
-Contiene dettagli inutili che vorremmo
ignorare
-Dipende da costanti non note
vogliamo darne una visione
più astratta (tasso di crescita)
Paragonare tra loro algoritmi
Abbiamo una scala di complessità:
...
2n
...
n3
n2
n log n
n
log n
1
vogliamo inserire ogni
algoritmo in questa scala
Un algoritmo può richiedere tempi diversi per input
della stessa taglia. Ad esempio il tempo per ordinare
n oggetti può dipendere dal loro ordine iniziale.
...
2n
...
n3
n2
n log n
n
log n
1
complessità massima
complessità media
complessità minima
Nell’analizzare la complessità tempo di un
algoritmo siamo interessati a come aumenta
il tempo al crescere della taglia n dell’input.
Siccome per valori “piccoli” di n il tempo
richiesto è comunque poco, ci interessa
soprattutto il comportamento per valori
“grandi” di n (il comportamento asintotico)
Inoltre, siccome la velocità del processore
influisce sul tempo calcolo per una costante
moltiplicativa noi valuteremo la complessità
a meno di una tale costante.
Questo giustifica le seguenti definizioni:
Notazione asintotica O
(limite superiore asintotico)
( g (n))  { f (n) : esistono c  0 ed n0 tali che
0  f (n)  cg (n) per ogni n  n0 }
cg (n)
f (n)
n0
O(g(n))
Scriveremo f(n) = O(g(n)) per dire che f(n) è
una delle funzioni dell’insieme O(g(n))
f(n) = O(g(n))
si legge:
f(n) è “o grande” di g(n)
Se f(n) = O(g(n)) rappresenta il tempo calcolo
richiesto da un algoritmo diciamo che
O(g(n)) è un limite superiore asintotico per la
complessità tempo di tale algoritmo.
esempi
f (n)  2n  5n  5  O(n )
2
2
infatti 0  2n  5n  5  cn
per c = 4 ed n0 = 5
Vedremo che in generale per a2 > 0
2
2
f (n)  a2 n  a1n  a0  O(n )
2
f (n)  2  sin n  O(1)
infatti 0  2  sin n  c 1
per c = 3 ed n0 = 1
2
Notazione asintotica .
(limite inferiore asintotico)
( g (n))  { f (n) : esistono c  0 ed n0 tali che
f (n)  cg (n)  0 per ogni n  n0 }
f (n)
cg (n)
n0
Scriveremo f(n) = (g(n)) per dire che f(n) è
una delle funzioni dell’insieme (g(n)).
f(n) = (g(n))
si legge:
f(n) è “omega” di g(n)
Se f(n) = (g(n)) rappresenta il tempo
calcolo richiesto da un algoritmo diciamo che
(g(n)) è un limite inferiore asintotico per la
complessità tempo di tale algoritmo.
esempi
f (n)  2n  5n  5  (n )
2
2
2
2
0

cn

2
n
 5n  5
infatti
per c = 1 ed n0 = 10
Vedremo che in generale se a2 > 0
f (n)  a2 n  a1n  a0  (n )
2
f (n)  2  sin n  (1)
infatti 0  c 1  2  sin n
per c = 1 ed n0 = 1
2
Notazione asintotica .
(limite asintotico stretto)
( g (n))  O( g (n))  ( g (n))  { f (n) : esistono
c1 , c2  0 ed n0 tali che per ogni n  n0
0  c1 g (n)  f (n)  c2 g (n)}
c2 g (n)
f (n)
c1 g (n)
n0
Scriveremo f(n) = (g(n)) per dire che f(n) è
una delle funzioni dell’insieme (g(n)).
f(n) = (g(n))
si legge:
f(n) è “theta” di g(n)
Se f(n) = (g(n)) rappresenta il tempo calcolo
richiesto da un algoritmo diciamo che (g(n))
è un limite asintotico stretto per la
complessità tempo di tale algoritmo.
esempi
2n  5n  5  O(n )
2
2
2n 2  5n  5  (n 2 )
2n 2  5n  5  (n 2 )
Dunque
0  c1n  2n  5n  5  c2 n
2
2
2
per c1 = 1, c2 = 4 ed n0 = 10
2  sin n  (1)
2  sin n  O(1)
Dunque 2  sin n  (1)
f (n)  2n  5n  5  (n ) altrimenti
2
3
0  c1n  2n  5n  5
3
2
2
5
5
c1   2  3
n n
n
per ogni n  n0 allora
per ogni n  n0. Assurdo!
f (n)  2n 2  5n  5  (n) altrimenti
0  2n 2  5n  5  c2 n per ogni n  n0 allora
5 5
c2
per ogni n  n0. Assurdo!
2  2 
n n
n
Metodo del limite
Spesso è possibile determinare dei limiti
asintotici calcolando il limite di un rapporto.
Ad esempio se lim n f (n) / g (n)  k  0
allora per ogni  > 0 esiste n0 tale che per n ≥ n0
k    f ( n) / g ( n)  k  
Preso 0 <  < k e posto c1 = k   e c2 = k +
c1 g (n)  f (n)  c2 g (n)
e quindi f ( n)  ( g ( n))
f ( n)
  diciamo che f (n)   ( g (n))
Se lim n
g ( n)
ed in questo caso
f (n)  ( g (n)) ma f (n)  ( g (n))
f ( n)
Se lim n
 0 diciamo che f (n)  o( g (n))
g ( n)
ed in questo caso
f (n)  O( g (n)) ma f (n)  ( g (n))
Attenzione: quando il limite del rapporto non
esiste questo metodo non si può usare.
k
k
f
(
n
)

a
n

...

a
n

a


(
n
)
In generale
k
1
0
per ogni funzione polinomiale di grado k con
coefficiente ak > 0.
Inoltre
k
h
(n )  (n ) per k  h
(a )  (b ) per a  b
n
n
(log a n)  (log b n) per ogni a e b
perché log a n  log a b log b n
(n log n)  (n )
k
k
Per 0 < h < k e 1 < a < b :
O(log n)  O(n )  O(n ) 
h
k
 O(n log n)  O(a )  O(b )
k
n
n
(log n)  (n )  (n ) 
h
k
 (n log n)  (a )  (b )
k
n
n
Useremo le notazioni asintotiche anche
all’interno delle formule.
In questo caso le notazioni O(f(n)), Ω(f(n)) e
ϴ(f(n)) stanno ad indicare una qualche funzione
appartenente a tali insiemi e di cui non ci
interessa conoscere la forma esatta ma solo il
comportamento asintotico.
Ad esempio T(n)=n2+O(n) significa che T(n) è
la somma di n2 e di una funzione che cresce al
più linearmente.