L’analisi asintotica aiuta a comprendere la complessità degli algoritmi

Analisi asintotica

L’analisi asintotica consente di descrivere il comportamento di una funzione per argomenti molto elevati. E’ un’analisi utilizzata in matematica e in informatica. In matematica è usata per descrivere il limite asintotico superiore di una funzione. In informatica viene utilizzata nell’analisi degli algoritmi per valutare la complessità degli algoritmi. Dal punto di vista formale l’analisi asintotica è indicata con la notazione O (lettera “o” maiuscola) che può essere letta con la frase “nell’ordine di”. Facciamo alcuni esempi pratici:

O(1) indica un numero di passi per arrivare alla soluzione. Ad esempio, un algoritmo usato per determinare se un numero è pari o dispari.

O(n) indica un numero di passi n per arrivare alla soluzione. Ad esempio, un algoritmo usato per la ricerca 

lineare di un elemento in una lista non ordinata.

O(n2) indica un numero di passi n2 per arrivare alla soluzione. Ad esempio, un algoritmo usato per l’ordinamento (sort) degli elementi tramite insertion sort.

L’analisi asintotica consente di descrivere in modo approssimativo la complessità di un algoritmo senza tenere in conto i dati di input e le costanti. Si può, ad esempio, dire che un algoritmo O(n) è meno complesso dell’algoritmo O(n2). L’analisi è caratterizzata da un certo grado di approssimazione, dovuto all’eliminazione dei fattori costanti, che tuttavia non inficia la sua validità nel fornire una descrizione della complessità dell’algoritmo. Ad esempio, prendiamo il caso di un algoritmo che richieda un numero di passi (o righe di codice) T(n)=n2+2n+1 per giungere alla soluzione. Non conoscendo l’entità degli elementi n della serie l’analista ha due possibilità per valutare la complessità dell’algoritmo:

Ipotesi sui dati di input. Fare una ipotesi sull’entità n dei dati di input per calcolare il numero di passi peggiore (Worst) e quello medio (Average). Il risultato dell’analisi è fortemente soggettivo in quanto deriva dall’ipotesi formulata dall’analista.

Analisi asintotica. Astrarre dall’entità dei dati di input e classificare la complessità dell’algoritmo facendolo tendere asintoticamente all’infinito tramite l’analisi asintotica. Pur essendo una misura approssimativa è considerata una valida soluzione di analisi per le sue caratteristiche di facilità di calcolo, universalità di applicazione e oggettività del risultato.

Nell’analisi asintotica un algoritmo che richieda un numero di operazioni T(n)=n2+2n+1 può essere descritto semplicemente come O(n2) in quanto facendo tendere all’infinito la funzione la componente (2n+1) influenza in modo minimo sulla dimensione della funzione. Il grado di approssimazione della complessità dell’algoritmo è pertanto considerato accettabile nel caso di un numero elevato di operazioni da svolgere. L’analisi asintotica non va confusa con i benchmark.