25+ algoritmi essenziali, organizzati per il problema che risolvono

Spunto: 25+ Essential Algorithms Explained in 40 Minutes.

Imparare gli algoritmi come una lista di nomi serve a poco. È molto più utile organizzarli per il tipo di problema che risolvono.

Nella pratica, infatti, raramente ci si domanda:

"Mi ricordo come funziona quicksort?"

La domanda reale è più spesso:

"Devo ordinare questi dati: quale approccio ha senso?"

Oppure:

"Devo trovare il percorso più breve", "questa ricerca viene ripetuta migliaia di volte?", "sto ricalcolando continuamente gli stessi risultati?"

Questo articolo è quindi una mappa mentale: non vuole sostituire un corso di algoritmi, ma aiutare a riconoscere rapidamente le famiglie più importanti e i loro compromessi.

Prima di iniziare: cosa significa O(n)?

Quando diciamo che un algoritmo è O(n), O(log n) oppure O(n²), stiamo descrivendo come cresce il suo costo al crescere della quantità di dati.

In modo molto semplificato:

O(1)        costo circa costante
O(log n)    cresce molto lentamente
O(n)        cresce proporzionalmente ai dati
O(n log n)  tipico dei buoni algoritmi di ordinamento
O(n²)       può diventare rapidamente costoso
O(2^n)      crescita esponenziale: diventa presto impraticabile

La notazione Big O non dice quanto impiega esattamente un programma in millisecondi. Serve soprattutto per confrontare come scalano algoritmi diversi quando l'input diventa grande.

1. Ordinamento: mettere i dati nell'ordine giusto

Bubble sort

Confronta ripetutamente elementi adiacenti e li scambia se sono nell'ordine sbagliato.

5  2  4  1
↓
2  5  4  1
↓
2  4  5  1
...

Complessità tipica:

O(n²)

È semplice da spiegare, ma raramente è una buona scelta pratica.

Selection sort

Cerca il minimo nella parte non ancora ordinata e lo sposta nella posizione corretta.

Anche questo è:

O(n²)

Ha però una caratteristica interessante: effettua relativamente pochi scambi. Può quindi avere senso in casi particolari in cui le scritture sono molto costose, anche se normalmente esistono alternative migliori.

Insertion sort

Prende un elemento alla volta e lo inserisce nella posizione corretta nella parte già ordinata.

Nel caso generale è:

O(n²)

ma sui dati piccoli o quasi ordinati può essere molto efficiente. Per questo viene spesso usato come componente di algoritmi ibridi.

Merge sort

Divide l'insieme in due metà, ordina ricorsivamente le due parti e poi le fonde.

8 3 6 2 7 1
   ↓ divide
8 3 6 | 2 7 1
   ↓
...
   ↓ merge
1 2 3 6 7 8

Ha complessità garantita:

O(n log n)

Nella forma classica su array richiede memoria aggiuntiva O(n).

È inoltre stabile se implementato preservando l'ordine degli elementi equivalenti: due elementi considerati uguali mantengono il loro ordine relativo originale.

Quicksort

Sceglie un pivot, dispone da una parte gli elementi minori e dall'altra quelli maggiori, poi ripete ricorsivamente il procedimento.

In media:

O(n log n)

Nel caso peggiore:

O(n²)

Con una buona strategia di partizionamento il caso medio è molto favorevole. Inoltre lavora bene con la cache della CPU ed è normalmente implementabile senza un array ausiliario grande quanto l'input.

Una versione didattica in C#:

static void QuickSort(int[] values, int low, int high)
{
    if (low >= high)
        return;

    int pivot = values[high];
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        if (values[j] <= pivot)
        {
            i++;
            (values[i], values[j]) = (values[j], values[i]);
        }
    }

    int pivotIndex = i + 1;
    (values[pivotIndex], values[high]) =
        (values[high], values[pivotIndex]);

    QuickSort(values, low, pivotIndex - 1);
    QuickSort(values, pivotIndex + 1, high);
}

È un esempio utile per capire l'algoritmo, non un invito a riscrivere Array.Sort().

Heap sort

Costruisce una struttura chiamata heap e la usa per estrarre progressivamente gli elementi nell'ordine corretto.

Garantisce:

O(n log n)

anche nel caso peggiore e può lavorare in place con memoria ausiliaria costante.

Non è stabile e, nella pratica, tende ad avere una località di memoria meno favorevole di quicksort.

Cosa usa .NET?

Per gli array, Array.Sort() usa un introspective sort, o introsort: combina più strategie.

In sostanza:

• insertion sort per partizioni molto piccole;
• quicksort nel caso normale;
• heapsort se la ricorsione diventa troppo profonda, evitando così il caso peggiore quadratico di quicksort.

Lo stesso meccanismo viene usato da List<T>.Sort() attraverso Array.Sort().

Nella maggior parte dei programmi conviene quindi usare le primitive della libreria e implementare manualmente questi algoritmi solo per studio o quando esiste un'esigenza molto specifica.

2. Ricerca: trovare un elemento

Ricerca lineare

Scorre gli elementi uno dopo l'altro finché trova quello cercato.

O(n)

Funziona anche con dati non ordinati.

Per una singola ricerca su una collezione piccola può essere esattamente la soluzione giusta.

Ricerca binaria

Se i dati sono ordinati, possiamo confrontare l'elemento cercato con quello centrale ed eliminare ogni volta metà dello spazio di ricerca.

1 3 5 7 9 11 13 15
      ↑

Complessità:

O(log n)

In C# esiste Array.BinarySearch().

Attenzione però: ordinare ha un costo. Se abbiamo dati non ordinati e dobbiamo fare una sola ricerca, ordinarli in O(n log n) soltanto per poter eseguire poi una ricerca binaria può essere peggio di una semplice scansione O(n).

La ricerca binaria diventa particolarmente interessante quando i dati sono già ordinati oppure quando eseguiamo molte ricerche sullo stesso insieme.

Ricerca tramite hash

Se dobbiamo fare molte ricerche per chiave esatta, spesso non serve ordinare affatto.

Strutture come:

Dictionary<TKey, TValue>
HashSet<T>

utilizzano una tabella hash.

Una ricerca ha costo O(1) medio, anche se il caso peggiore teorico può essere peggiore.

Questo evidenzia una regola importante: a volte il vero miglioramento non arriva da un algoritmo più sofisticato, ma dalla struttura dati giusta.

3. Grafi: collegamenti, percorsi e dipendenze

Un grafo è formato da:

• vertici o nodi;
• archi che collegano i nodi.

Molti problemi che non sembrano "grafi" in realtà lo sono:

• strade tra città;
• collegamenti tra pagine web;
• dipendenze tra pacchetti software;
• amicizie in un social network;
• stati possibili di un gioco;
• collegamenti tra stanze in una mappa.

Indichiamo normalmente con V il numero di vertici e con E il numero di archi.

BFS — Breadth-First Search

La ricerca in ampiezza esplora il grafo livello per livello, usando una coda.

        A
      /   \
     B     C
    / \     \
   D   E     F

Ordine BFS possibile:

A, B, C, D, E, F

Costo:

O(V + E)

In un grafo non pesato, o in cui tutti gli archi hanno lo stesso costo, BFS trova il percorso con il minor numero di archi.

Una versione minimale in C#:

static void Bfs(
    Dictionary<int, List<int>> graph,
    int start)
{
    var visited = new HashSet<int> { start };
    var queue = new Queue<int>();
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.WriteLine(node);

        foreach (int next in graph[node])
        {
            if (visited.Add(next))
                queue.Enqueue(next);
        }
    }
}

DFS — Depth-First Search

La ricerca in profondità segue un ramo il più possibile prima di tornare indietro.

Può essere implementata:

• con ricorsione;
• con uno Stack<T> esplicito.

Costo:

O(V + E)

È molto utile per:

• attraversare strutture;
• trovare componenti connesse;
• rilevare cicli;
• esplorare labirinti;
• costruire un ordinamento topologico in un DAG.

Ordinamento topologico

Se un grafo orientato descrive dipendenze e non contiene cicli — cioè è un DAG, Directed Acyclic Graph — possiamo disporre i nodi in un ordine che rispetti tutte le dipendenze.

Esempio:

Compila libreria
      ↓
Compila applicazione
      ↓
Esegui test
      ↓
Crea pacchetto

Gli approcci classici sono:

• DFS;
• algoritmo di Kahn, basato sul numero di archi entranti.

È il tipo di problema che compare nei sistemi di build, nei prerequisiti e nella pianificazione di attività dipendenti.

Dijkstra

Trova il percorso minimo da un nodo sorgente agli altri nodi in un grafo con pesi non negativi.

Con una coda a priorità:

O((V + E) log V)

È adatto, per esempio, a una rete stradale quando ogni tratto ha un costo positivo.

In .NET, PriorityQueue<TElement, TPriority> è una struttura naturale per implementarlo.

Dijkstra non va usato direttamente con archi di peso negativo.

Bellman-Ford

Risolve anch'esso il problema del percorso minimo da una sorgente, ma accetta anche pesi negativi.

Costo:

O(V · E)

È quindi più lento di Dijkstra.

Ha però un'altra proprietà importante: può rilevare la presenza di cicli di peso negativo raggiungibili dalla sorgente. Se un ciclo del genere può essere percorso indefinitamente, il concetto stesso di cammino minimo diventa problematico.

Floyd-Warshall

Quando non ci interessa una sola sorgente ma vogliamo conoscere le distanze minime tra tutte le coppie di nodi, un algoritmo classico è Floyd-Warshall.

Costo:

O(V³)

È semplice ed elegante e può gestire archi negativi, purché non esistano cicli negativi rilevanti.

Per grafi molto grandi e sparsi possono essere preferibili altri approcci, ma Floyd-Warshall è fondamentale per capire la programmazione dinamica applicata ai grafi.

A*

A* cerca un percorso verso un obiettivo usando:

1. il costo già sostenuto;
2. una euristica che stima il costo ancora necessario per arrivare alla destinazione.

È molto usato nel pathfinding:

partenza → → → destinazione

Con una buona euristica può esplorare molti meno nodi di Dijkstra.

Non significa però che sia sempre "più veloce": il comportamento dipende dalla qualità dell'euristica e dalla struttura del problema.

Se l'euristica non sovrastima mai il costo reale rimanente — è quindi ammissibile — A* può mantenere la garanzia di trovare un percorso ottimo nelle condizioni appropriate.

Kruskal e Prim

Entrambi trovano un minimum spanning tree (MST): un insieme di archi che collega tutti i nodi di un grafo pesato con il minor costo totale possibile, senza creare cicli.

Kruskal:

1. ordina gli archi per peso;
2. prende prima quelli meno costosi;
3. evita quelli che creerebbero un ciclo.

Per controllare rapidamente i cicli usa spesso una struttura Union-Find, chiamata anche Disjoint Set Union.

Costo tipico:

O(E log E)

Prim invece costruisce l'albero progressivamente partendo da un nodo e aggiungendo ogni volta il collegamento meno costoso verso un nodo non ancora incluso.

Con heap e liste di adiacenza:

O(E log V)

Percorso minimo e MST non sono la stessa cosa: Dijkstra minimizza un percorso da una sorgente; Kruskal e Prim minimizzano il costo complessivo necessario per connettere l'intero grafo.

4. Programmazione dinamica: non risolvere due volte lo stesso problema

La programmazione dinamica, o dynamic programming (DP), è utile quando un problema presenta soprattutto due caratteristiche:

1. può essere scomposto in sottoproblemi;
2. gli stessi sottoproblemi ricompaiono più volte.

In molti problemi di ottimizzazione compare anche una proprietà chiamata sottostruttura ottima: una soluzione ottimale può essere costruita usando soluzioni ottimali di sottoproblemi.

Esistono due approcci principali.

Memoization — top-down

Si parte dal problema completo e si usa la ricorsione, memorizzando i risultati già calcolati.

Tabulation — bottom-up

Si parte dai casi più piccoli e si costruiscono progressivamente quelli più grandi, normalmente con un array o una tabella.

La programmazione dinamica può ridurre enormemente il lavoro, ma non trasforma automaticamente qualunque algoritmo esponenziale in uno polinomiale: dipende da quanti stati distinti deve comunque esplorare.

Fibonacci

La versione ricorsiva ingenua calcola più volte gli stessi valori:

Fib(5)
├─ Fib(4)
│  ├─ Fib(3)
│  └─ Fib(2)
└─ Fib(3)   ← già calcolato

Con memoization:

static readonly Dictionary<int, long> cache = new();

static long Fib(int n)
{
    if (n <= 1)
        return n;

    if (cache.TryGetValue(n, out long value))
        return value;

    value = Fib(n - 1) + Fib(n - 2);
    cache[n] = value;

    return value;
}

Il numero di sottoproblemi distinti diventa lineare:

O(n)

L'esempio serve a mostrare il principio; per Fibonacci, in produzione, esistono soluzioni iterative ancora più semplici e con memoria costante.

Knapsack 0/1 — problema dello zaino

Abbiamo oggetti con:

• un peso;
• un valore.

Lo zaino ha una capacità massima e ogni oggetto può essere preso interamente oppure lasciato.

L'obiettivo è massimizzare il valore trasportato.

La classica soluzione dinamica richiede:

O(n · W)

dove W è la capacità dello zaino.

Questa complessità viene detta pseudo-polinomiale, perché dipende dal valore numerico di W, non soltanto dalla quantità di bit necessaria per rappresentarlo.

È una distinzione tecnica importante: O(n · W) non significa che il problema generale dello zaino 0/1 sia diventato "facile" in senso teorico.

LCS — Longest Common Subsequence

Trova la sottosequenza più lunga presente, nello stesso ordine, in due sequenze.

Esempio:

ABCDEF
AEDF

LCS = ADF

È strettamente collegato ai problemi di confronto tra sequenze e di costruzione delle differenze tra testi.

Dire semplicemente che "diff usa LCS" sarebbe però troppo forte: gli strumenti reali possono utilizzare algoritmi diversi. Un esempio fondamentale è l'algoritmo di Myers, progettato per trovare uno shortest edit script ed estremamente importante nel confronto tra file.

Distanza di Levenshtein

Misura il numero minimo di:

• inserimenti;
• cancellazioni;
• sostituzioni;

necessari per trasformare una stringa in un'altra.

gatto
↓
matto

una sola sostituzione:

distanza = 1

È utile per:

• correzione ortografica;
• ricerca approssimata;
• suggerimenti del tipo "forse cercavi...";
• confronto tra stringhe.

5. Greedy: scegliere il meglio adesso

Un algoritmo greedy prende a ogni passo quella che sembra la scelta migliore in quel momento e non torna indietro.

Questo approccio è spesso molto efficiente, ma c'è un problema:

una sequenza di scelte localmente ottime non produce necessariamente una soluzione globalmente ottima.

Per usare correttamente un algoritmo greedy bisogna quindi sapere — o dimostrare — che il problema possiede le proprietà necessarie.

Kruskal e Prim sono esempi di algoritmi greedy.

Huffman coding

La codifica di Huffman costruisce un albero che assegna codici più corti ai simboli più frequenti e più lunghi a quelli meno frequenti.

È un algoritmo fondamentale nella compressione senza perdita.

Zaino frazionario

È simile al problema dello zaino 0/1, ma qui possiamo prendere anche una frazione di un oggetto.

In questo caso funziona una strategia greedy:

1. calcolare valore / peso;
2. ordinare gli oggetti per questo rapporto;
3. prendere prima quelli con rapporto maggiore.

Questa strategia produce l'ottimo per lo zaino frazionario.

Per lo zaino 0/1, invece, la stessa idea può fallire.

Activity selection

Abbiamo attività con un orario di inizio e uno di fine e vogliamo sceglierne il maggior numero possibile senza sovrapposizioni.

La scelta greedy corretta consiste nel prendere ogni volta l'attività che finisce prima tra quelle compatibili.

È un buon esempio perché mostra che "greedy" non significa semplicemente "scegli il numero più grande": significa trovare una regola locale che possa essere dimostrata corretta.

6. Divide et impera: spezzare il problema

Lo schema è:

DIVIDE
↓
risolvi i sottoproblemi
↓
COMBINA

Merge sort è l'esempio classico, ma non è l'unico.

Anche quicksort appartiene a questa famiglia: divide i dati usando il pivot e risolve separatamente le partizioni.

Altri esempi importanti sono:

• ricerca binaria;
• algoritmo di Strassen per la moltiplicazione di matrici;
• FFT, Fast Fourier Transform;
• problema della coppia di punti più vicina nel piano, risolvibile in O(n log n) invece dell'approccio ingenuo O(n²).

La caratteristica essenziale è che i sottoproblemi risultanti possono essere risolti in modo sostanzialmente indipendente.

7. Backtracking: prova, controlla, torna indietro

Il backtracking è utile quando dobbiamo cercare una soluzione tra molte combinazioni possibili.

Lo schema è:

prova una scelta
↓
è ancora possibile arrivare a una soluzione?
├─ sì  → continua
└─ no  → annulla la scelta e provane un'altra

È quindi una ricerca sistematica che elimina presto i rami impossibili.

Esempi classici:

• Sudoku;
• problema delle N regine;
• generazione di permutazioni;
• ricerca di combinazioni con vincoli;
• alcuni risolutori di labirinti.

N regine

Dobbiamo mettere N regine su una scacchiera N × N senza che possano attaccarsi.

Una ricerca completamente ingenua proverebbe un enorme numero di disposizioni.

Con backtracking, appena una regina appena inserita entra in conflitto con una precedente, quel ramo viene abbandonato senza completare inutilmente il resto della scacchiera.

Il backtracking non rende automaticamente facile un problema combinatorio: nel caso peggiore il numero di possibilità può rimanere enorme. Il vantaggio è potare appena possibile le alternative che sappiamo già non poter funzionare.

8. Algoritmi su stringhe: cercare testo senza confrontare tutto

Ricerca ingenua

Per cercare una parola dentro un testo possiamo provare a confrontarla partendo da ogni posizione possibile.

Nel caso peggiore il costo può arrivare a:

O(n · m)

dove:

• n è la lunghezza del testo;
• m è la lunghezza del pattern.

KMP — Knuth-Morris-Pratt

KMP sfrutta la struttura interna del pattern per evitare di ricontrollare caratteri che sappiamo già essere compatibili.

Dopo una fase di preparazione del pattern, la ricerca può essere eseguita in:

O(n + m)

È un ottimo esempio di algoritmo che migliora le prestazioni non "andando più veloce", ma evitando lavoro già implicitamente svolto.

Rabin-Karp

Calcola un hash delle finestre di testo e lo confronta con l'hash del pattern.

È particolarmente interessante quando vogliamo cercare più pattern oppure capire come le funzioni hash possano essere usate anche negli algoritmi, non soltanto nelle tabelle hash.

9. Tre piccoli algoritmi matematici che vale la pena conoscere

Non tutti gli algoritmi fondamentali lavorano su grandi strutture dati.

Algoritmo di Euclide

Calcola il massimo comune divisore:

MCD(a, b) = MCD(b, a mod b)

finché il secondo valore diventa zero.

È antico, semplicissimo e sorprendentemente efficiente.

Crivello di Eratostene

Trova tutti i numeri primi fino a un limite n.

Parte dai numeri naturali ed elimina progressivamente i multipli dei primi già trovati.

La complessità è circa:

O(n log log n)

È molto più efficiente che verificare indipendentemente ogni numero provando tutti i divisori possibili.

Esponenziazione rapida

Per calcolare:

a^n

non serve moltiplicare a per se stesso n-1 volte.

Sfruttando la rappresentazione binaria dell'esponente possiamo ridurre il numero di moltiplicazioni a:

O(log n)

Questa tecnica compare anche nell'aritmetica modulare e nella crittografia.

Come orientarsi tra tutti questi algoritmi

Memorizzare i nomi serve meno che riconoscere la struttura del problema.

Una piccola mappa mentale può essere questa:

| Se il problema dice... | Pensa prima a... |
|---|---|
| "devo ordinare" | algoritmi di sorting / `Array.Sort()` |
| "devo trovare un elemento" | ricerca lineare, binaria o hashing |
| "ho nodi e collegamenti" | BFS, DFS, algoritmi su grafi |
| "voglio il percorso minimo" | BFS, Dijkstra, Bellman-Ford, A* |
| "devo collegare tutto al costo minimo" | Kruskal, Prim |
| "ho dipendenze" | ordinamento topologico |
| "ricalcolo gli stessi sottoproblemi" | programmazione dinamica |
| "ogni scelta locale può essere definitiva" | greedy, ma solo se è dimostrabile |
| "posso dividere in problemi indipendenti" | divide et impera |
| "devo esplorare combinazioni con vincoli" | backtracking |
| "devo cercare pattern nel testo" | KMP, Rabin-Karp |

Una domanda fondamentale viene ancora prima dell'algoritmo:

Come sono strutturati i miei dati?

Un Dictionary può eliminare la necessità di una ricerca lineare. Una PriorityQueue rende naturale Dijkstra. Una struttura Union-Find rende efficiente Kruskal.

Algoritmi e strutture dati vanno quasi sempre pensati insieme.

Il punto pratico

Conoscere un algoritmo non significa ricordarne a memoria ogni riga di codice.

Significa soprattutto saper riconoscere:

1. quale problema risolve;
2. quali condizioni richiede;
3. quanto costa al crescere dei dati;
4. quali compromessi introduce;
5. se la libreria standard offre già una buona implementazione.

Bubble sort, Dijkstra, Levenshtein e A* sembrano argomenti molto diversi. In realtà insegnano tutti la stessa lezione: prima di scrivere codice, bisogna capire la struttura del problema.

L'algoritmo giusto nasce quasi sempre da quella struttura, non dal nome che ricordiamo da un libro.