Analisi di Complessità degli Algoritmi

shiny ditto

Posted on 29/8/2022, 03:51

.

Advanced Member

Group: Amministratore

Posts: 8,544

Status: Offline

Analisi di Complessità degli Algoritmi

Una delle cose più importanti che ho imparato all'Università è valutare la complessità di un algoritmo ed è sicuramente un aspetto che fa la differenza tra un programmatore di medio-basso livello e uno invece di medio-alto.
Finite le superiori ero consapevole che uno stesso risultato poteva essere ottenuto con algoritmi diversi, ma non avevo troppa idea che due algoritmi diversi possono risolvere lo stesso problema usando un numero di risorse radicalmente diverse.
Imparare a creare algoritmi che ottimizzano il più possibile il consumo di risorse è fondamentale per chiunque voglia fare il programmatore.
Ricordo che alla Laurea Triennale il mio professore di Algoritmi e Strutture Dati fece un esempio che mi colpì molto, immaginando due macchine: una con elevate prestazioni e l'altra invece con basse prestazioni.
Sulla macchina potente è stato inserito la risoluzione di un algoritmo fortemente inefficiente, mentre sulla macchina più debole è stato inserito la risoluzione di un algoritmo fortemente efficiente: il risultato è stato che la macchina meno prestante ha calcolato più velocemente il risultato.
Quindi non pensate di scampare alle vostre responsabilità di programmatori sperando solo in un miglioramento delle risorse hardware!

I tipi di Complessità

Per poter capire quante risorse consuma un nostro algoritmo è fondamentale distinguere due tipi di Complessità Computazionale:

Complessità Spaziale: Riferito alla memoria occupata da un algoritmo e quindi tiene conto di tutte le variabili che vengono usate dall'algoritmo, fortunatamente questo tipo di complessità è maggiormente gestibile dall'Hardware e anche dal programmatore, ad esempio ricorrendo alla deallocazione delle variabili che non servono durante l'algoritmo.

Complessità Temporale: Riferito al numero di istruzioni eseguite dal nostro algoritmo. Non fatevi confondere dal nome, i secondi non centrano nulla! Su questa i programmatori lavorano maggiormente ed è meno gestibile dall'Hardware

Le tre tipologie di Scenari

Talvolta gli algoritmi non richiedono sempre lo stesso numero di istruzioni o di memoria e quindi sostanzialmente la complessità computazionale può variare in un range di valori:

Caso migliore: Il numero minimo di istruzioni che un algoritmo può eseguire (indicato con Ω);

Caso medio: Il numero medio di istruzioni che un algoritmo può eseguire (indicato con Θ);

Caso peggiore: Il numero massimo di istruzioni che un algoritmo può eseguire (indicato con Ο)

Ad esempio immaginiamo un algoritmo di ricerca lineare di un numero all'interno di un vettore di elementi.
Il vettore è composto da N numeri, ad esempio N = 5:

Vettore = [10,24,23,14,75]

Se il numero che cerco è il valore 10 avrò il caso migliore poiché mi verrà restituito immediatamente il risultato.
Se il numero che cerco è l'ultimo (75) oppure non è presente avrà eseguito 5 operazioni di confronto invece che 1 come al caso precedente.
La media tra questi valori che posso individuare rappresenta invece il caso medio.

In ambito informatico solitamente si analizzano i casi peggiori poiché sono quelli che riescono a creare una metrica di confronto tra algoritmi per valutare la loro efficienza.

Un Esempio pratico

Per aiutarvi a capire meglio vi riporto un esempio pratico che può aiutarvi a capire come funziona in modo molto elementare il calcolo della complessità temporale:

Dato il seguente codice:

HTML

for(int i = 0; i<n; i++) {
for(int j = 1; j<n; j++) {
M1[i][j] = M2[i][j-1];
}
}

Nella complessità temporale vengono conteggiate solamente le operazioni di confronto e di assegnamento, mentre le operazioni di dichiarazione di una variabile e di input/output non vengono conteggiate.

In questo caso abbiamo un primo ciclo for che ha la seguente complessità computazionale:

i = 0 : comporta un'unica istruzione 1;

i < n : comporta n+1 confronti;

i++ : comporta n incrementi

Quindi la complessità di questo primo ciclo for sarà: 1 + n + 1 + n = 2n + 2

Mentre nel secondo ciclo for dobbiamo tenere conto che verrà eseguito n volte e quindi moltiplichiamo n per:

j = 1 : comporta un'unica istruzione 1;

j < n : comporta n confronti;

j++ : comporta n-1 incrementi;

M1[i][j] = M2[i][j-1] comporta un'unica istruzione

Quindi la complessità del secondo ciclo for sarà: n * (1 + n + n - 1 + 1) = n * (2n + 1) = 2n² + n

Facendo la somma dei due cicli for: 2n + 2 + 2n² + n = 2n² + 3n + 2

L'ordine di grandezza nel caso peggiore diventa O(n²) e quindi si tratta di una complessità polinomiale di tipo quadratica.

Scala della Complessità:

Spesso per semplificare la visualizzazione della complessità per chi fa parte del settore si usa l'ordine di grandezza per specificare vari tipi di scala: in questo caso ci sono i principali: