Un algoritmo è una sequenza finita e non ambigua di passi che trasforma dati iniziali in un risultato verificabile. I dieci metodi di questo articolo sono fra i più noti perché esprimono idee riutilizzabili: ridurre lo spazio di ricerca, dividere un problema, visitare una rete, conservare risultati parziali o sfruttare le frequenze.
Non esiste un algoritmo migliore in assoluto. Un metodo è efficace quando è corretto per i dati disponibili, rispetta i vincoli di tempo e memoria e garantisce il risultato richiesto. Lo pseudocodice serve a capire l’idea: nelle applicazioni reali conviene usare librerie consolidate e testate.
Come leggere le complessità
La notazione O(...) descrive come cresce il costo al crescere dell’ingresso, non un tempo in secondi. In questo articolo n indica il numero di elementi, V i vertici di un grafo, E i suoi archi, m la lunghezza di un modello di testo, W la capacità dello zaino, k il numero di simboli distinti e L la lunghezza del messaggio.
| Ordine | Lettura pratica |
|---|---|
O(1) | Il costo non cresce con la dimensione dell’ingresso. |
O(log n) | Ogni passo riduce fortemente il problema, spesso della metà. |
O(n) | Il lavoro cresce in proporzione agli elementi. |
O(n log n) | Costo tipico degli ordinamenti generali efficienti. |
O(n²) | Il costo può crescere rapidamente su ingressi grandi. |
1. Algoritmo di Euclide
Obiettivo. Calcolare il massimo comune divisore di due interi senza elencarne tutti i divisori.
Idea fondamentale. Se a = qb + r, i divisori comuni di a e b sono gli stessi di b e del resto r. Si sostituisce quindi la coppia con (b, a mod b) finché il resto diventa zero.
Pseudocodice
MCD(a, b)
a ← valore_assoluto(a)
b ← valore_assoluto(b)
MENTRE b ≠ 0
(a, b) ← (b, a mod b)
RESTITUISCI aEsempio svolto. Per MCD(252, 105): 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0. L’ultimo resto non nullo è 21.
Complessità. Tempo O(log min(a,b)) e memoria O(1) nella versione iterativa.
Quando usarlo. Per semplificare frazioni, verificare la coprimalità, calcolare periodi e preparare operazioni di aritmetica modulare. La versione estesa trova anche coefficienti di Bézout e inversi modulari.
Limite da ricordare. Bisogna definire il caso MCD(0,0), che non è determinato; l’algoritmo non è di per sé un sistema crittografico.
2. Ricerca binaria
Obiettivo. Trovare un valore in una sequenza ordinata senza controllare ogni elemento.
Idea fondamentale. Si confronta il valore cercato con l’elemento centrale. Il confronto elimina la metà che non può contenere la risposta; si ripete sul solo intervallo rimasto.
Pseudocodice
RICERCA_BINARIA(A, x)
sinistra ← 0
destra ← lunghezza(A) − 1
MENTRE sinistra ≤ destra
centro ← sinistra + parte_intera((destra − sinistra) / 2)
SE A[centro] = x RESTITUISCI centro
SE A[centro] < x
sinistra ← centro + 1
ALTRIMENTI
destra ← centro − 1
RESTITUISCI non_trovatoEsempio svolto. In [3, 8, 12, 17, 23, 31] si cerca 23. Il centro vale 12, quindi si scarta la parte sinistra; il nuovo centro vale 23 e la ricerca termina.
Complessità. Tempo O(log n) e memoria O(1) nella forma iterativa.
Quando usarlo. Su vettori ordinati con accesso rapido per indice; anche per trovare il primo o l’ultimo elemento che soddisfa una proprietà monotona.
Limite da ricordare. L’ordinamento è una precondizione. Su dati che cambiano continuamente, il costo per mantenerli ordinati può superare il vantaggio della ricerca.
3. Merge sort (ordinamento per fusione)
Obiettivo. Ordinare una sequenza con un tempo prevedibile e conservando l’ordine relativo degli elementi equivalenti.
Idea fondamentale. Si divide la sequenza in due metà, si ordinano ricorsivamente le metà e si fondono confrontando ogni volta i primi elementi non ancora copiati.
Pseudocodice
MERGE_SORT(A)
SE lunghezza(A) ≤ 1 RESTITUISCI A
metà ← parte_intera(lunghezza(A) / 2)
sinistra ← MERGE_SORT(A[0 ... metà−1])
destra ← MERGE_SORT(A[metà ... fine])
RESTITUISCI FONDI(sinistra, destra)
FONDI(L, R)
risultato ← sequenza vuota
FINCHÉ L e R non sono vuote
sposta in risultato il minore dei primi elementi
aggiungi gli elementi rimasti
RESTITUISCI risultatoEsempio svolto. [8, 3, 5, 1] viene diviso in [8,3] e [5,1]. Le metà diventano [3,8] e [1,5]; la fusione produce [1,3,5,8].
Complessità. Tempo O(n log n) nel caso migliore, medio e peggiore; memoria ausiliaria tipica O(n). È stabile se, a parità, si prende prima l’elemento della metà sinistra.
Quando usarlo. Quando servono prestazioni prevedibili e stabilità, su liste collegate o nell’ordinamento esterno di dati troppo grandi per la memoria.
Limite da ricordare. Su vettori richiede memoria aggiuntiva; per piccoli blocchi un ordinamento semplice può avere costanti migliori.
4. Quicksort (ordinamento rapido)
Obiettivo. Ordinare velocemente in memoria sfruttando una partizione effettuata sul posto.
Idea fondamentale. Si sceglie un pivot, si dispongono prima gli elementi non maggiori e dopo quelli maggiori, quindi si ordinano ricorsivamente le due parti. Un pivot casuale riduce la probabilità di partizioni molto sbilanciate.
Pseudocodice
QUICKSORT(A, basso, alto)
SE basso ≥ alto RESTITUISCI
p ← PARTIZIONE_CASUALE(A, basso, alto)
QUICKSORT(A, basso, p − 1)
QUICKSORT(A, p + 1, alto)
PARTIZIONE_CASUALE sposta un pivot casuale nella sua
posizione definitiva e restituisce il suo indiceEsempio svolto. Con pivot 5, [8,3,5,1,7] viene partizionato concettualmente in [3,1] + [5] + [8,7]. Ordinando le due parti si ottiene [1,3,5,7,8].
Complessità. Tempo atteso O(n log n), caso peggiore O(n²). La partizione può essere sul posto; lo stack è atteso O(log n) ma può arrivare a O(n).
Quando usarlo. Per vettori in memoria quando contano velocità media, località della cache e poca memoria ausiliaria. Le librerie applicano spesso varianti ibride.
Limite da ricordare. Non è normalmente stabile e una scelta sistematicamente cattiva del pivot provoca il caso quadratico. Nel software reale è preferibile la funzione di ordinamento della libreria.
5. Ricerca in ampiezza (BFS)
Obiettivo. Visitare un grafo per livelli e trovare un cammino con il minimo numero di archi da una sorgente.
Idea fondamentale. Una coda conserva i vertici scoperti ma non ancora esplorati. Tutti i vertici a distanza d vengono elaborati prima di quelli a distanza d + 1.
Pseudocodice
BFS(G, sorgente)
per ogni vertice v: visitato[v] ← falso
visitato[sorgente] ← vero
distanza[sorgente] ← 0
CODA.inserisci(sorgente)
FINCHÉ CODA non è vuota
u ← CODA.estrai_primo()
PER ogni v adiacente a u
SE non visitato[v]
visitato[v] ← vero
distanza[v] ← distanza[u] + 1
padre[v] ← u
CODA.inserisci(v)Esempio svolto. Se A è collegato a B e C, B a D e C a E, BFS da A visita prima A, poi B e C, infine D ed E. Il vettore dei padri ricostruisce uno dei cammini minimi.
Complessità. Con liste di adiacenza, tempo O(V+E) e memoria O(V), oltre alla memoria del grafo.
Quando usarlo. Per distanze in grafi non pesati, gradi di separazione, diffusione per livelli, labirinti con mosse tutte dello stesso costo e verifica di bipartizione.
Limite da ricordare. Non calcola il cammino di costo minimo quando gli archi hanno pesi differenti; l’ordine fra vertici dello stesso livello dipende dall’ordine delle adiacenze.
6. Ricerca in profondità (DFS)
Obiettivo. Esplorare completamente un ramo prima di tornare indietro e provare le alternative.
Idea fondamentale. Uno stack, esplicito o fornito dalla ricorsione, conserva il percorso corrente. Quando un vertice non offre nuovi vicini si torna al precedente.
Pseudocodice
DFS(G, sorgente)
visitato[sorgente] ← vero
PILA ← [sorgente]
FINCHÉ PILA non è vuota
u ← PILA.estrai_ultimo()
ELABORA(u)
PER ogni v adiacente a u
SE non visitato[v]
visitato[v] ← vero
padre[v] ← u
PILA.inserisci(v)Esempio svolto. Nel grafo A–B, A–C, B–D e C–E, una possibile DFS percorre A, B, D, torna ad A e prosegue con C, E. Un diverso ordine dei vicini produce un ordine valido differente.
Complessità. Con liste di adiacenza, tempo O(V+E) e memoria O(V). Una ricorsione molto profonda può esaurire lo stack del linguaggio.
Quando usarlo. Per componenti connesse, rilevamento di cicli, ordinamento topologico di grafi aciclici, esplorazione di labirinti e problemi di backtracking.
Limite da ricordare. Non garantisce il cammino più corto. Nei grafi si deve segnare ciò che è stato visitato per evitare cicli infiniti.
7. Algoritmo di Dijkstra
Obiettivo. Calcolare le distanze minime da una sorgente in un grafo con pesi non negativi.
Idea fondamentale. Si mantiene una distanza provvisoria per ogni vertice. Una coda con priorità estrae quello più vicino non ancora consolidato; rilassare un arco prova se raggiungere il vicino attraverso quel vertice costa meno.
Pseudocodice
DIJKSTRA(G, sorgente)
per ogni v: distanza[v] ← infinito
distanza[sorgente] ← 0
CODA_PRIORITÀ.inserisci(0, sorgente)
FINCHÉ la coda non è vuota
(du, u) ← estrai_minimo()
SE du ≠ distanza[u] CONTINUA
PER ogni arco (u, v, peso)
nuovo ← du + peso
SE nuovo < distanza[v]
distanza[v] ← nuovo
padre[v] ← u
inserisci(nuovo, v)Esempio svolto. Con archi A–B:4, A–C:1, C–B:2, B–D:1 e C–D:5, il percorso minimo da A a D è A–C–B–D e costa 4.
Complessità. Con lista di adiacenza e heap binario, tempo O((V+E) log V). Distanze e padri occupano O(V); nella variante semplice mostrata, le voci superate nell’heap possono richiedere fino a O(E), oltre al grafo O(V+E).
Quando usarlo. Per reti stradali senza costi negativi, instradamento, dipendenze con costi e qualsiasi problema riconducibile a cammini minimi pesati.
Limite da ricordare. Anche un solo peso negativo rende invalida la garanzia. In quel caso servono algoritmi come Bellman–Ford; per soli pesi uguali basta BFS.
8. Zaino 0/1 con programmazione dinamica
Obiettivo. Scegliere oggetti indivisibili massimizzando il valore senza superare una capacità intera.
Idea fondamentale. Problemi diversi riutilizzano gli stessi sottoproblemi. dp[c] conserva il miglior valore ottenibile con capacità c. Per ogni oggetto si percorrono le capacità al contrario, così lo stesso oggetto non viene preso due volte.
Pseudocodice
ZAINO_01(oggetti, W)
dp[0 ... W] ← 0
PER ogni (peso, valore) negli oggetti
PER c DA W A peso, IN ORDINE DECRESCENTE
dp[c] ← massimo(dp[c], dp[c − peso] + valore)
RESTITUISCI dp[W]Esempio svolto. Con capacità 5 e oggetti (peso 2, valore 3), (3,4), (4,5), i primi due riempiono lo zaino e valgono 7, più di ogni singolo oggetto.
Complessità. Tempo O(nW) e memoria O(W). È pseudo-polinomiale: dipende dal valore numerico di W, non soltanto dal numero di cifre che lo rappresentano.
Quando usarlo. Per budget o capacità interi moderati, selezione di progetti e allocazione di risorse quando ogni scelta può essere presa al massimo una volta.
Limite da ricordare. Con capacità enorme la tabella diventa impraticabile; inoltre il modello semplice non rappresenta dipendenze fra oggetti o valori non additivi.
9. Knuth–Morris–Pratt (KMP)
Obiettivo. Trovare tutte le occorrenze esatte di un modello in un testo senza tornare indietro nel testo.
Idea fondamentale. Una tabella dei prefissi registra, per ogni posizione del modello, la lunghezza del più lungo prefisso che è anche suffisso. Dopo una mancata corrispondenza si riusa questa informazione invece di ricominciare da zero.
Pseudocodice
COSTRUISCI_PREFISSI(P)
prefisso[0] ← 0; j ← 0
PER i DA 1 A lunghezza(P) − 1
MENTRE j > 0 E P[i] ≠ P[j]
j ← prefisso[j − 1]
SE P[i] = P[j] ALLORA j ← j + 1
prefisso[i] ← j
RESTITUISCI prefisso
KMP(testo T, modello P)
prefisso ← COSTRUISCI_PREFISSI(P); j ← 0
PER i DA 0 A lunghezza(T) − 1
MENTRE j > 0 E T[i] ≠ P[j]
j ← prefisso[j − 1]
SE T[i] = P[j] ALLORA j ← j + 1
SE j = lunghezza(P)
SEGNALA i − lunghezza(P) + 1
j ← prefisso[j − 1]Esempio svolto. Cercando ABABAC in ABABABAC, dopo la mancata corrispondenza KMP sa che il suffisso ABAB è anche un prefisso utile. Trova l’occorrenza che inizia all’indice 2, contando da zero.
Complessità. Costruzione della tabella e ricerca richiedono insieme O(n+m); la tabella usa O(m) memoria.
Quando usarlo. Per ricerca esatta in testi lunghi o flussi, soprattutto con modelli che contengono molte ripetizioni e quando serve una garanzia lineare.
Limite da ricordare. Cerca corrispondenze esatte, non somiglianze o errori. Lo pseudocodice assume un modello non vuoto; per una ricerca breve le funzioni ottimizzate del linguaggio sono normalmente preferibili.
10. Codifica di Huffman
Obiettivo. Assegnare codici binari più corti ai simboli frequenti e più lunghi a quelli rari, mantenendo una decodifica univoca.
Idea fondamentale. Si inseriscono le frequenze in una coda con priorità e si uniscono ripetutamente i due nodi meno frequenti. Il percorso sinistra/destra nell’albero risultante fornisce un codice prefisso: nessun codice è il prefisso di un altro.
Pseudocodice
HUFFMAN(frequenze)
Q ← heap_minimo con una foglia per simbolo
FINCHÉ dimensione(Q) > 1
x ← Q.estrai_minimo()
y ← Q.estrai_minimo()
z ← nodo(frequenza(x) + frequenza(y), x, y)
Q.inserisci(z)
RESTITUISCI Q.estrai_minimo()Esempio svolto. Con frequenze A:5, B:2, C:1, D:1, un possibile codice è A=0, B=10, C=110, D=111. I 9 simboli richiedono 15 bit invece dei 18 bit di un codice fisso a due bit.
Complessità. Con k simboli distinti, costruire l’albero costa O(k log k); codificare o decodificare un messaggio costa O(L). Albero e tabella occupano O(k).
Quando usarlo. Come componente di formati di compressione e quando sono note frequenze affidabili. È ottimale fra i codici prefissi che assegnano un numero intero di bit a ogni simbolo.
Limite da ricordare. Non sfrutta da solo ripetizioni lunghe o contesto; su file piccoli il costo di memorizzare l’albero può annullare il risparmio. Per dati reali si usano formati e librerie standard.
Quale algoritmo scegliere?
Questa tabella non sostituisce l’analisi dei vincoli, ma offre un primo orientamento.
| Problema | Scelta iniziale | Motivo |
|---|---|---|
| Massimo comune divisore e coprimalità | Algoritmo di Euclide | Riduce rapidamente la coppia usando i resti. |
| Valore in una sequenza ordinata | Ricerca binaria | Scarta metà dell’intervallo a ogni confronto. |
| Ordinamento stabile e prevedibile | Merge sort (ordinamento per fusione) | Garantisce sempre tempo proporzionale a n log n. |
| Ordinamento veloce di un vettore in memoria | Quicksort (ordinamento rapido) | Ha ottime prestazioni medie e partizione sul posto. |
| Cammino minimo in un grafo non pesato | Ricerca in ampiezza (BFS) | La visita per livelli garantisce il minor numero di archi. |
| Esplorazione completa, cicli o backtracking | Ricerca in profondità (DFS) | Segue un ramo fino in fondo e torna alle alternative. |
| Cammino minimo con pesi non negativi | Algoritmo di Dijkstra | Consolida sempre la distanza provvisoria più piccola. |
| Scelta ottima con capacità intera moderata | Zaino 0/1 con programmazione dinamica | Riusa i risultati dei sottoproblemi sovrapposti. |
| Ricerca esatta di un modello in un testo | Knuth–Morris–Pratt (KMP) | Non ricontrolla caratteri del testo già acquisiti. |
| Codice prefisso basato sulle frequenze | Codifica di Huffman | Assegna meno bit ai simboli più frequenti. |
Confrontare questi algoritmi mostra una lezione generale: prima si definiscono con precisione ingresso, risultato e vincoli; poi si sceglie l’idea che sfrutta meglio la struttura del problema. Correttezza e precondizioni vengono prima della velocità.