Analisi dell’algoritmo
L’analisi dell’efficienza di un algoritmo può essere eseguita in due fasi diverse, prima dell’implementazione e dopo l’implementazione, come
A priori analysis – Questa è definita come analisi teorica di un algoritmo. L’efficienza dell’algoritmo viene misurata assumendo che tutti gli altri fattori, ad esempio la velocità del processore, siano costanti e non abbiano alcun effetto sull’implementazione.
Un’analisi a posteriori – Questa è definita come analisi empirica di un algoritmo. L’algoritmo scelto viene implementato utilizzando un linguaggio di programmazione. Successivamente l’algoritmo scelto viene eseguito sulla macchina di destinazione. In questa analisi, vengono raccolte le statistiche effettive come il tempo di esecuzione e lo spazio necessario.
L’analisi dell’algoritmo si occupa del tempo di esecuzione di varie operazioni coinvolte. Il tempo di esecuzione di un’operazione può essere definito come il numero di istruzioni del computer eseguite per operazione.
Complessità dell’algoritmo
Supponiamo che X sia trattato come un algoritmo e N sia trattato come la dimensione dei dati di input, il tempo e lo spazio implementati dall’algoritmo X sono i due fattori principali che determinano l’efficienza di X.
Fattore tempo – Il tempo è calcolato o misurato contando il numero di operazioni chiave come i confronti nell’algoritmo di ordinamento.
Fattore spazio – Lo spazio è calcolato o misurato contando lo spazio massimo di memoria richiesto dall’algoritmo.
La complessità di un algoritmo f(N) fornisce il tempo di esecuzione e/o lo spazio di memoria necessario all’algoritmo rispetto a N come dimensione dei dati di input.
Complessità spaziale
La complessità spaziale di un algoritmo rappresenta la quantità di spazio di memoria necessario all’algoritmo nel suo ciclo di vita.
Lo spazio necessario ad un algoritmo è uguale alla somma dei seguenti due componenti
Una parte fissa che è uno spazio richiesto per memorizzare certi dati e variabili (cioè variabili semplici e costanti, dimensione del programma ecc.), che non dipendono dalla dimensione del problema.
Una parte variabile è uno spazio richiesto dalle variabili, la cui dimensione dipende totalmente dalla dimensione del problema. Per esempio, lo spazio dello stack di ricorsione, l’allocazione dinamica della memoria ecc.
La complessità spaziale S(p) di qualsiasi algoritmo p è S(p) = A + Sp(I) dove A è trattato come la parte fissa e S(I) è trattato come la parte variabile dell’algoritmo che dipende dalla caratteristica di istanza I. Segue un semplice esempio che cerca di spiegare il concetto
Algoritmo
SUM(P, Q)Step 1 - STARTStep 2 - R ← P + Q + 10Step 3 - Stop
Qui abbiamo tre variabili P, Q e R e una costante. Quindi S(p) = 1+3. Ora lo spazio dipende dai tipi di dati dei tipi di costante e delle variabili date e sarà moltiplicato di conseguenza.
Complessità temporale
La complessità temporale di un algoritmo è la rappresentazione della quantità di tempo richiesta dall’algoritmo per essere eseguito fino al completamento. I requisiti di tempo possono essere denotati o definiti come una funzione numerica t(N), dove t(N) può essere misurato come il numero di passi, a condizione che ogni passo richieda un tempo costante.
Per esempio, nel caso dell’addizione di due interi a n bit, sono necessari N passi. Di conseguenza, il tempo totale di calcolo è t(N) = c*n, dove c è il tempo consumato per l’aggiunta di due bit. Qui, osserviamo che t(N) cresce linearmente all’aumentare della dimensione dell’input.
