COMPLESSITÀ COMPUTAZIONALE

PRESTAZIONI DEGLI ALGORITMI

Le prestazioni degli algoritmi possono essere confrontate con diversi metodi. Uno di questi consiste, semplicemente, nell’eseguire molti test per ogni algoritmo e nel confrontarne i tempi di esecuzione misurati.

Un altro metodo consiste nel confrontare i fattori di crescita delle stime di costo.

Per esempio, possiamo affermare che il tempo di ricerca è O(n) (O grande di n).

Questo significa che il tempo di ricerca, all’aumentare di n, è proporzionale al numero di elementi n nella lista. Di conseguenza ci aspettiamo che il tempo di ricerca risulti triplicato se la dimensione della lista aumenta di un fattore tre.

Se un algoritmo richiede O(n²) tempo, allora il suo tempo di esecuzione non cresce più del quadrato della dimensione della lista. 

La tabella illustra i valori con cui crescono le varie funzioni.
Si vede chiaramente che esiste una notevole differenza tra i problemi che richiedono algoritmi eseguibili in tempi che dipendono da potenze di n e quelli che richiedono tempi di tipo esponenziale.

Un fattore di crescita O(lg n) si ha per gli algoritmi simili alla ricerca binaria. La funzione lg (logaritmo in base 2) cresce di uno quando n raddoppia. Si ricordi che, con la ricerca binaria, è possibile ricercare fra il doppio dei valori con un confronto in più. Pertanto la ricerca binaria è un algoritmo di complessità O(lg n).