Contattori e accumulatori, complessità degli algoritmi

Contattori e accumulatori, complessità degli algoritmi

Contatori e accumulatori

Si tratta di variabili il cui contenuto viene rispettivamente incrementato di una quantità fissa e generalmente unitaria o di una quantità variabile; a scalare nel caso dei contatori, questi vengono detti se la quantità è negativa. Una tipica istruzione che implementa un contatore è + 1, mentre +← ← realizza un accumulatore.

Tabella di traccia

Tabella che permette di tenere traccia dei valori assunti dalle singole variabili durante l'esecuzione di un algoritmo su specifici valori di input; essa prevede una colonna per ogni variabile utilizzata dall'algoritmo, mentre sulle righe, una per ogni istruzione eseguita, viene annotato il valore assunto dalle singole variabili. Questo è uno strumento molto utile per verificare passo per passo la funzionalità di un algoritmo.

Complessità degli algoritmi

L'efficienza con cui diversi algoritmi risolvono uno stesso problema diventa rilevante quando la quantità di dati da elaborare diventa grande. In generale la complessità computazionale o efficienza viene valutata rispetto all'uso di risorse quali lo spazio, ovvero la memoria necessaria per l'esecuzione dell'algoritmo, e il tempo richiesto per l'esecuzione dell'algoritmo stesso. La risorsa critica è il tempo; esso viene calcolato in funzione del numero di operazioni elementari eseguite durante l'applicazione di un algoritmo su specifici dati di input.