Dopo aver analizzato la complessità in tempo di alcuni algoritmi possiamo osservare che
- il caso ottimo di un algoritmo è quasi sempre costante
- non sarebbe significativo per la bassa probabilità che ha di presentarsi
- il caso pessimo e il caso medio dipendono dalla dimensione dei dati
- è difficile calcolare con precisione le costanti moltiplicative
- per n piccolo è difficile decidere tra due algoritmi
- per n abbastanza grande la differenza di comportamento diventa evidente
Per dare una misura della complessità in tempo di un algoritmo si preferisce
- dare una misura approssimata del calcolo del tempo di esecuzione
- studiare il caso pessimo oppure il caso medio
- valutare il comportamento per sufficientemente grande…
- si introduce la complessità asintotica
Definizione
Una funzione è , e si legge è dell’ordine o grande di , se esistono una costante moltiplicativa ed un numero naturale tali che per una certa e per ogni
Esempio
Data la funzione , scegliendo opportunamente i valori (, ) si ha
allora per e quindi
In pratica
- le costanti moltiplicative diventano trascurabili
- le combinazioni lineari di funzioni diventano trascurabili
- è sufficiente individuare la funzione più pesante
- tutte le funzioni costanti sono dell’ordine
- tutte le funzioni lineari sono dell’ordine
- tutte le funzioni quadratiche sono dell’ordine
- …
La complessità in tempo viene riassunta in una funzione più significativa che rappresenta la complessità in tempo asintotica.
Esempi
Le costanti sono spropositate per evidenziare l’aspetto asintotico… della complessità
- , rifletti…
Elenco
Per tutte le semplificazioni che abbiamo adottato le funzioni di complessità veramente interessanti in ambito informatico sono poche
- , costante
- , sottologaritmica, meno di logaritmica
- , logaritmica
- , 0 < k < 1, sottolineare, meno di lineare
- , lineare
- , enne-log-enne
- , 1 < k < 2, meno di quadratica
- , quadratica
- , 2 < k < 3, meno di cubica
- , cubica
- , k ≥ 3, polinomiale
- , esponenziale
- , …
- , più che esponenziale
- , …