L'analisi di algoritmi

Quando si parla di analizzare un algoritmo, si intende misurare le risorse necessarie per eseguirlo ( tempo, spazio di memoria, ecc. ).

In questa pagina, per semplicità considero come risorsa soltanto il tempo di esecuzione dell'algoritmo. Un'altra risorsa da considerare, oltre il tempo, sarebbe lo spazio di memoria ma il discorso diventerebbe molto più complesso.

Poiché le risorse hanno un costo, dalla misura delle risorse si stima l'efficienza e il costo dell'algoritmo o del programma che lo implementa.

Un algoritmo è più efficiente, quando è caratterizzato da un costo più basso rispetto agli algoritmi alternativi.

Tuttavia, il tempo non è una buona misura del costo dell'algoritmo, perché il costo dell'algoritmo deve essere indipendente dalla macchina che lo esegue.

Ad esempio, se facessi girare lo stesso algoritmo su due computer con configurazione hardware differente, l'uno più veloce dell'altro, otterrei due misure diverse del costo. Quindi, non potrei nemmeno confrontare l'efficienza di due algoritmi diversi testati su computer differenti, perché la misura sarebbe influenzata dall'hardware della macchina utilizzata per misurarla.

Per risolvere il problema, si potrebbe utilizzare per la misurazione una macchina astratta universale e stimare il costo dell'algoritmo su questa macchina.

Supponendo che il costo di elaborazione di un istruzione sia uguale a 1, allora il costo di elaborazione dell'algoritmo è determinato dal numero di operazioni eseguite sulla macchina astratta.

La macchina di Turing. Un esempio di questo tipo è la macchina di Turing. Si tratta di un elaboratore in grado di svolgere un numero limitato di operazioni (andreaminini.com). Consente di confrontare l'efficienza degli algoritmi in modo omogeneo.

Più in generale, si potrebbe misurare l'efficienza con il numero delle operazioni elementari eseguite dall'algoritmo per risolvere il problema.

E' sicuramente una misura migliore del costo di un algoritmo rispetto al tempo.

Tuttavia, ci sono ancora diversi problemi da risolvere:

1. La tipologia delle istruzioni. Tutto dipende da cosa si intende per operazione elementare ( assegnazioni, calcolo aritmetico, operazioni relazionali, istruzioni semplici, ecc. ).

   Nota. Non esiste una definizione chiara di istruzione semplice. Ad esempio, l'istruzione "return" è un'istruzione semplice oppure no?

2. I cicli iterativi. Un ciclo iterativo è un gruppo di istruzioni ripetuto più volte.

   Esempio. In una struttura iterativa un gruppo di 5 istruzioni viene ripetuto per 100 volte. Sarebbe errato considerare soltanto le 5 istruzioni dell'algoritmo per misurare il costo di computazione. In realtà, l'algoritmo ne elabora 500 ( 5 istruzioni x 100 cicli ).

3. La dimensione dei dati in input. Il costo di un algoritmo non dipende soltanto dalle istruzioni ma anche dalla quantità dei dati in input da elaborare.

   Esempio. Un programma di 5 istruzioni elabora 10 record di un file. Un altro programma di 5 istruzioni elabora 1000 record di un file. I due programmi non hanno lo stesso costo di elaborazione. La dimensione dei dati in input influenza il costo computazione.

4. Il valore dell'input influisce sul computo. Non soltanto la dimensione ma anche i valori dei dati in input influiscono sulla computazione.

   Esempio. Le due addizioni 2+2 e 14324+21482 hanno costi computazionali diversi, pur essendo entrambe due operazioni aritmetiche con due dati in input.

Quindi, considerando anche questi fattori, ottengo una definizione di costo dell'algoritmo molto più evoluta.

Per calcolare il costo dell'algoritmo devo considerare sia il numero delle istruzioni elaborate, sia la dimensione dei dati in input.

Un esempio pratico

Nel seguente esempio è presente un programma con i relativi dati in input.

Lo scopo del programma è verificare la presenza del valore x=6 nel vettore V.