Funzione di complessità

La funzione di complessità è uno strumento utilizzato nell'informatica per l'analisi computazionale della complessità dell'algoritmo. La funzione di complessità consente di calcolare il numero di operazioni necessarie a un algoritmo per completare l'elaborazione di N dati ( dimensione dei dati ). La funzione di complessità è normalmente indicata con il simbolo O seguito dalla funzione di complessità stessa. La funzione di complessità può essere:

• Funzione di complessità lineare. È una funzione di complessità del tipo O ( N ). È detta "lineare" poiché la complessità cresce in modo lineare rispetto ai dati da elaborare come in una retta ( linea ). La complessità cresce in modo proporzionale alla dimensione dei dati. Ad esempio, per elaborare 2 bit impiega 2 unità di tempo, per elaborare 4 bit impiega 4 unità di tempo, per elaborare 8 bit impiega 8 unità di tempo, ecc.
• Funzione di complessità polinomiale. È una funzione di complessità del tipo O ( N^k ). In questo caso la complessità dell'algoritmo cresce in modo più che proporzionale alla dimensione dei dati. Ad esempio, per k=2 la funzione di complessità O ( N² ) cresce al quadrato dei dati in ingresso. Per elaborare 2 bit impiega 4 unità di tempo, per elaborare 4 bit impiega 16 unità di tempo, per elaborare 8 bit impiega 64 unità di tempo, ecc.
• Funzione di complessità esponenziale. È una funzione di complessità del tipo O ( k^N ). Questa funzione caratterizza gli algoritmi impossibili da utilizzare in caso di grandi quantità di dati. Nei problemi a complessità esponenziale il numero delle operazioni computazionali dell'algoritmo crescerebbe in modo esponenziale rispetto alla dimensione dei dati. Il tempo di elaborazione e il consumo di risorse potrebbe diventare proibitivo ( complessità esponenziale ). Ad esempio, sia k una costante pari a due ( k=2 ), per elaborare 2 bit l'algoritmo impiega 4 unità di tempo, per elaborare 4 bit impiega 16 unità di tempo, per elaborare 8 bit impiega 256 unità di tempo, ecc.

Ordine di elaborazione dei dati. A parità di dimensione dei dati N la complessità di un algoritmo è fortemente condizionata dall'ordine di elaborazione dei dati. Per questa ragione è necessario calcolare la complessità di un algoritmo prendendo in considerazione il caso migliore, il caso peggiore e il caso medio. Nel caso migliore i dati ricercati sono situati all'inizio della sequenza dei dati da elaborare ( vettore ). Sono quindi necessarie poche elaborazioni per giungere al risultato. Nel caso peggiore, viceversa, sono posti alla fine della sequenza dei dati da elaborare. In tale caso sono necessarie molte elaborazioni per giungere al risultato finale. Il caso medio, infine, prende in considerazione una situazione intermedia tra quella migliore e quella peggiore, ed è per questo considerato l'indicatore più realistico della complessità di un algoritmo.

Unità di tempo. Nel calcolo della complessità di un algoritmo è prassi associare la durata di un'operazione di calcolo a una unità di tempo. Ad esempio, 1 operazione = 1 nanosecondo. In tal modo il numero di operazioni effettuate dall'algoritmo consente di ottenere anche il tempo teorico di esecuzione dell'algoritmo, indipendentemente dall'hardware del computer utilizzato per eseguire l'algoritmo. Qualunque sia la potenza di un computer, dati due algoritmi A e B in grado di risolvere un medesimo problema ( efficacia ), l'algoritmo in grado di risolverlo con un minore numero di operazioni ( efficienza ) è sempre da considerarsi migliore ( algoritmo efficiente ).