Perché alcuni programmi sono velocissimi a svolgere un compito, mentre altri sembrano impiegare un'eternità per fare la stessa cosa? O perché, anche con computer sempre più potenti, alcune operazioni rimangono lente? La risposta sta nella complessità computazionale.

In parole semplici, la complessità computazionale è una misura delle risorse di calcolo necessarie per eseguire un algoritmo.

Quando parliamo di risorse, ci riferiamo principalmente a due aspetti:

1. lo spazio di memoria
2. il tempo di esecuzione

La soluzione ad un problema viene tradotta in un algoritmo, che poi viene implementato in un linguaggio di programmazione per diventare un programma eseguibile sul computer.

I concetti di complessità si applicano anche a modelli teorici come la Macchina di Turing.

Memoria vs. Tempo: quale dei due è più importante oggi?

Un tempo la memoria era una risorsa molto preziosa e limitata. Chi ha lavorato con computer di qualche decennio fa sa quanto fosse cruciale risparmiare anche un singolo byte. Oggi, invece, lavoriamo con macchine che hanno gigabyte di memoria a disposizione e per questo motivo il tempo di esecuzione tende ad essere la risorsa preponderante da considerare. Il tempo, a differenza della memoria che può essere liberata e riutilizzata, è una risorsa non riutilizzabile e non va sprecata.

Tuttavia non si può trascurare l'occupazione di memoria, perché una sua gestione inefficiente può causare problemi e impattare sulle performance del software.

Comprendere la complessità computazionale non è un puro esercizio accademico. Dal punto di vista pratico ci serve principalmente per due motivi:

1. scegliere l'algoritmo migliore: spesso un problema può essere risolto da diversi algoritmi e la complessità ci permette di confrontarli e di determinare quello più efficiente. Maggiore efficienza significa minore utilizzo di risorse (ovvero minore complessità)

2. valutare la rilevanza pratica di un algoritmo: se richiede settimane o mesi per completare un'elaborazione, anche se teoricamente corretto, ha una valenza quasi esclusivamente teorica e difficilmente potrà essere utilizzato in produzione.

Ma come si misura la complessità?

Valutare l'occupazione di memoria è relativamente intuitivo: possiamo calcolare lo spazio in base ai tipi di dati utilizzati e alle dimensioni delle strutture dati, sommando i singoli risultati ottenuti.

Misurare il tempo di esecuzione è più articolato. La prima idea potrebbe essere quella di far girare il programma su un computer e misurare il tempo con un cronometro. Tuttavia questa misurazione non è oggettiva e dipende da fattori esterni all'algoritmo stesso quali:

1. la potenza della macchina: un programma girerà più velocemente su un computer più potente
2. il carico della macchina: se il computer sta eseguendo altre operazioni pesanti contemporaneamente (come un rendering video), il tempo di esecuzione sarà maggiore
3. l'ottimizzazione del compilatore: il modo in cui il codice viene tradotto in linguaggio macchina può influenzare notevolmente le prestazioni (rispetto ad un linguaggio interpretato).

Questi fattori esterni rendono difficile ottenere un dato obiettivo che dipenda solo dall'algoritmo.

Per superare questo problema, gli informatici hanno sviluppato una metodologia diversa: invece di misurare il tempo effettivo, si valuta il costo di un algoritmo in base alla dimensione dei dati di input, indicata solitamente con la lettera N.

Questa valutazione si concentra sulle operazioni dominanti ovvero quelle che vengono eseguite il maggior numero di volte all'interno dell'algoritmo.

Ad esempio, in un algoritmo di ordinamento, le operazioni dominanti potrebbero essere i confronti e gli scambi.

La relazione tra l'impiego di risorse e la dimensione dei dati di input viene espressa tramite una funzione di costo f(N).

Questa funzione è tipicamente crescente (all'aumentare di N il costo aumenta) e non negativa.

La bellezza di questa funzione è che può essere valutata analizzando il codice, senza doverlo effettivamente eseguire su una macchina specifica. Inoltre funziona sia per programmi reali che per modelli puramente teorici.

Quello che ci interessa di più non è il valore esatto della funzione per un N specifico, ma il suo andamento al crescere di N, soprattutto quando N diventa molto grande (tende all'infinito).

Questa è l'analisi asintotica in cui trascuriamo fattori moltiplicativi e costanti additive per concentrarci sull'ordine di grandezza della funzione.

Tale ordine ci dice come "scala" l'algoritmo all'aumentare della dimensione dei dati.

Esempi di ordini di grandezza (dalla migliore alla peggiore performance asintotica) includono

1. costante: il tempo rimane lo stesso indipendentemente da N (spesso irrealizzabile)
2. logaritmico: il tempo cresce molto lentamente all'aumentare di N
3. lineare: il tempo cresce linearmente con N (se raddoppi N raddoppi anche il costo)
4. quadratico e cubico: il tempo cresce più velocemente con potenze di 2 e 3
5. esponenziale: il tempo cresce enormemente al crescere di N, rendendo l'algoritmo poco praticabile per dati di dimensioni significative.

Capire l'ordine di grandezza di un algoritmo è fondamentale per prevedere le sue prestazioni su grandi quantità di dati.

Ma non dimentichiamo la configurazione dei dati da trattare.

La funzione di costo dipende non solo dalla dimensione N, ma anche da come i dati sono distribuiti e per questo motivo consideriamo tipicamente tre scenari:

1. caso ottimo: corrisponde alla configurazione dei dati che porta al minor tempo di esecuzione possibile. Ad esempio, in un algoritmo di ordinamento, il caso ottimo potrebbe essere quando i dati sono già ordinati rispetto al criterio richiesto
2. caso pessimo: corrisponde alla configurazione dei dati che porta al tempo di esecuzione massimo. Di fatto rappresenta una sorta di limite superiore oltre il quale l'algoritmo non potrà spingersi. Nell'esempio i dati sono ordinati inversamente rispetto al criterio richiesto
3. caso medio: rappresenta il tempo di esecuzione con una distribuzione variabile dei dati (spesso casuale). É la situazione più interessante nella pratica, anche se richiede un'analisi più complessa.

Infine dobbiamo considerare la complessità intrinseca dei problemi.

Ogni problema ha una sua "difficoltà" di base, che condiziona gli algoritmi che possiamo sviluppare per risolverlo.

Questa complessità intrinseca fissa un limite inferiore alla complessità di qualsiasi algoritmo che possa risolvere quel problema: si possono trovare algoritmi con una complessità superiore a quella del problema (che non funzionano bene) o al massimo con la stessa complessità del problema.

Questi ultimi si chiamano algoritmi ottimi in ordine di grandezza.

Ovviamente non riusciremo mai a trovare un algoritmo la cui complessità sia inferiore a quella intrinseca del problema che deve risolvere.

Facciamo un esempio semplice: trovare l'elemento minimo in un array di N elementi non ordinati.

Per essere sicuri di trovare il minimo dobbiamo per forza esaminare tutti gli N elementi. Non si può fare l'operazione in un tempo costante o logaritmico, perché non riusciremmo a "vedere" tutti i dati. La complessità intrinseca di questo problema è lineare (O(N)) e non si può scendere al di sotto di essa.

Fare di peggio certamente sì.

In sintesi, la conoscenza della complessità computazionale è fondamentale per un informatico perché permette di valutare e scegliere algoritmi efficienti e capire i limiti teorici e pratici della risoluzione dei problemi.

[VIDEO YOUTUBE]

[PODCAST]