Complessità di un algoritmo

Dato un algoritmo, una questione di grande importanza pratica è quanto tempo sia necessario per eseguirlo. Un' altra risorsa che nella programmazione degli elaboratori assume una grande importanza pratica, oltre al tempo, è la quantità di memoria necessaria per mantenere tutte le informazioni iniziali, intermedie e finali relative al problema che si sta risolvendo. Occasionalmente, possono assumere rilievo anche altri tipi di risorse, come la banda di comunicazione e il numero di porte logiche utilizzate, ma la risorsa che il più delle volte si è interessati a misurare è il tempo. La quantità di risorse necessaria per l'esecuzione di un algoritmo è la sua complessità computazionale, che è in relazione diretta con la difficoltà del problema. La difficoltà effettiva di un problema sarà data dalla complessità computazionale del miglior algoritmo che potrà essere scritto per risolvere il problema.
Il tempo di esecuzione di un algoritmo può essere misurato per ogni dato d'ingresso. Dopo aver scomposto il problema da risolvere in un insieme di operazioni elementari si deve:

definire il tempo necessario per eseguire ciascuna delle operazioni elementari
profilare l'algoritmo, cioè analizzando l'algoritmo trovare il numero di volte che ogni operazione elementare deve essere eseguita

Il tempo totale di esecuzione sarà: Ttotale = (Toperazione elemtare₁ x N_numero di volte che si ripete₁) + (T₂ x N₂)+……...

Trovare il tempo di esecuzione di un' operazione elementare è però tutt' altro che banale. Vanno fatte delle ipotesi dipendenti dalla tecnologia utilizzata, infatti se un algoritmo lo eseguo con "carta e penna" ci metterò più tempo che con un computer. Per analizzare un algoritmo è quindi necessario disporre di un modello della tecnologia che verrà utilizzata per realizzarlo; tale modello deve descrivere le risorse utilizzate e il loro costo. E' consuetudine adottare un modello generico di macchina ad accesso casuale (alla memoria) con un processore singolo, in inglese random-access machine (RAM). In pratica, tale modello è ispirato abbastanza fedelmente al funzionamento della stragrande maggioranza dei processori utilizzati dagli elaboratori elettronici. In questo modello computazionale il tempo necessario per accedere a qualsiasi punto della memoria è costante (è sempre uguale).
Inoltre ogni operazione elementare richiede la stessa quantità di risorse, per essere eseguita. Queste ipotesi rendono relativamente più semplice l' analisi della complessità computazionale dell'Algoritmo.
Nel caso in cui l'analisi della complessità computazionale è fatta su tutti gli ingressi possibili e non su ingressi dati, le cose cambiano sostanzialmente. Per esempio trovare il MCD di due numeri col metodo euclideo è molto più semplice su numeri piccoli, che su numeri con molte cifre decimali. Quello che interessa quindi non è tanto studiare il tempo e lo spazio impiegati da una particolare esecuzione di un algoritmo, quanto fare delle statistiche su tutte le possibili esecuzioni, cioè per ogni possibile ingresso. Solitamente la complessità di un algoritmo viene "misurata" sul caso peggiore; solo in subordine può a volte interessare anche il caso medio. Il tempo di esecuzione nel caso peggiore di un algoritmo è il più lungo tempo di esecuzione su tutti gli ingressi di dimensione n. Analogamente, lo spazio di esecuzione nel caso peggiore è il più grande spazio richiesto su tutti gli ingressi di dimensione n.
Ci sono tre buone ragioni per concentrare l'analisi di un algoritmo sul caso peggiore:

Le risorse del caso peggiore costituiscono un limite superiore alle risorse che l'esecuzione dell'algoritmo richiederà mai. Conoscerle ci da una garanzia che non ne serviranno di più
Per alcuni algoritmi, il caso peggiore si verifica abbastanza spesso. Per esempio, nella ricerca di un'informazione in una base di dati, il caso peggiore dell'algoritmo si verificherà spesso se quell'informazione non è presente.
Spesso e volentieri, il caso medio è all' incirca tanto cattivo quanto il caso peggiore. Solo quando è vero il contrario, cioè quando il caso peggiore è "raro" o improbabile, ha senso calcolare le risorse richieste nel caso medio.

Per saperne di più consulta i seguenti approfondimenti:

Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.