Cos’è l’analisi asintotica?
In matematica l’analisi asintotica consente di confrontare il tasso di crescita (comportamento asintotico) di una funzione nei confronti di un’altra, è utilizzato in Analisi algoritmica.
Per usare l’analisi asintotica devo trasformare il tempo di esecuzione dell’algoritmo in una funzione
- In genere la funzione
misura il numero di comandi eseguiti dall’algoritmo.
- Se la ricorrenza è espressa con = allora si userà la notazione
, se con < allora si userà O, se con > allora si userà - Le equazioni di ricorrenza rappresentano lo strumento matematico per descrivere il tempo di esecuzione
di tali algoritmi in funzione della dimensione dell’input .