Tempo di esecuzione algoritmo
Il tempo di esecuzione dell'algoritmo è il lasso di tempo impiegato da un algoritmo per completare l'elaborazione, dall'inizio alla fine. Il tempo di esecuzione di un algoritmo è anche detto complessità temporale ( complessità algoritmo ) ed è misurato in secondi. I principali fattori determinanti del tempo di esecuzione di un algoritmo sono i seguenti:
- Dimensione dati in input. Quanti più dati in input l'algoritmo deve elaborare, tanto maggiore è il suo tempo di esecuzione. La dimensione dei dati è misurata nel numero di bit necessari alla loro rappresentazione binaria.
- Sequenza di istruzioni. Quante più istruzioni l'algoritmo deve elaborare, tanto maggiore è il suo tempo di esecuzione.
Per la misura del tempo di esecuzione di un algoritmo ci si basa sullo studio delle caratteristiche dell'algoritmo a parità di dimensione dei dati in input. Uno dei principali metodi di misurazione è il conteggio dei passi elementari ossia ogni volta che l'algoritmo esegue un'operazione elementare. Alcuni esempi di operazioni elementari sono l'assegnazione delle variabili, un'operazione condizionata, un'operazione aritmetica, la lettura di un dato, ecc. È opportuno distinguere il numero dei passi elementari dal numero delle righe o dei comandi dell'algoritmo. Ad esempio, il seguente codice è composto da 2 operazioni semplici che realizzano un ciclo in cui la stessa operazione aritmetica di assegnazione della variabile viene svolta 10 volte.
For j=1 to 10 {
totale=totale+1
}
Le due operazioni semplici sono l'istruzione For per realizzare il ciclo e l'istruzione di assegnazione della variabile 'totale'. I passi elementari sono, invece, undici (1+10). Il primo passo elementare viene effettuato nell'esecuzione dell'istruzione For (1) che dà inizio al ciclo. Successivamente, il ciclo ripete per dieci volte l'operazione di assegnazione della variabile 'totale' (10). In conclusione, il tempo di esecuzione dell'algoritmo non è determinato dal numero delle righe di codice ( 2 ) bensì dal numero di volte che sono eseguite nel corso della computazione ( 11 ).
Tempo polinomiale. Data una dimensione di n numeri razionali in input, il tempo di esecuzione è un tempo polinomiale se esiste un numero intero k tale che il tempo di esecuzione dell'algoritmo è pari a O ( nk ). Se ( k=1 ) il tempo di esecuzione è detto tempo lineare. Quando l'algoritmo completa l'esecuzione in un tempo polinomilale, allora si dice che l'algoritmo è calcolabile in tempo polinomiale.
Misurazione effettiva del tempo di esecuzione. La misurazione del tempo reale di esecuzione di un algoritmo è fortemente influenzata anche dalle capacità computazionali della macchina ( computer ) in cui viene eseguito l'algoritmo. Ciò rende particolarmente difficile il confronto omogeneo delle performance tra algoritmi diversi. Per questa ragione si preferisce utilizzare il tempo di esecuzione teorico fissando il tempo di esecuzione di ogni istruzione a una stessa misura temporale. Ad esempio, può essere attribuito un tempo standard pari a 1 micro secondo per ogni passo elementare elaborato dagli algoritmi a parità di dimensione dei dati in input.
