Complessità in tempo asintotica
Dopo aver analizzato la complessità in tempo di alcuni algoritmi fondamentali possiamo osservare che
- il caso ottimo di un algoritmo è quasi sempre costante (e comunque non sarebbe significativo…)
- il caso pessimo (medio) dipende dalla dimensione dei dati
- è difficile calcolare con precisione le costanti moltiplicative
- per n piccolo è difficile decidere tra due algoritmi mentre per n abbastanza grande…
Si preferisce allora dare una misura della complessità in tempo di un algoritmo dando
- la misura approssimata del calcolo del tempo di esecuzione T(n)
- studiando il suo comportamento per n sufficientemente grande in modo che la discussione sia significativa...
Definizione
Si introduce la complessità asintotica e la notazione O(f(n))
una funzione g(n) è O(f(n)), si legge g(n) è dell'ordine o grande di f(n),
se esistono una costante moltiplicativa c ed un numero naturale n0 tali che
g(n) ≤ c*f(n), per una certa c e per ogni n≥n0
Esempio
Data la funzione
g(n)=2n2+4n+2
con i valori
c=2.1 e n≥41
si ha
g(41) = 3528
2.1(41)2 = 3530.1
allora2.1(41)2 = 3530.1
g(n)=2n2+4n+2 ε O(n2)
In pratica
- le costanti moltiplicative diventano trascurabili e così le combinazioni lineari di funzioni
- tutte le funzioni lineari sono dell'ordine O(n)
- tutte le funzioni quadratiche sono dell'ordine O(n2)
- ...
Esempi
Le costanti sono spropositate per evidenziare l'aspetto asintotico... della complessità- T1(n)=2n+400log2n ε O(n)
- T2(n)=2n3+400n ε O(n3)
- T3(n)=20000+log10n ε O(logn)
- T4(n)=3n+400n4+100000000 ε O(2n)
