Tassi di Crescita, Non Costi Assoluti
Big O: Misurare Quanto Velocemente Crescono i Costi
La notazione Big O misura il tasso di crescita del costo di un algoritmo — non il costo assoluto.
La domanda a cui Big O risponde: quando la dimensione dell'input N raddoppia, il lavoro raddoppia? Si quadruplica? Rimane stabile?
La 'O' sta per 'ordine di grandezza.' L'espressione dentro le parentesi descrive la forma della curva di crescita.
Classi di complessità chiave:
- O(1) — costante: il costo non cresce. Esempio: cercare un valore per indice in un array. Che l'array abbia 10 elementi o 10 milioni, una ricerca rimane una ricerca.
- O(N) — lineare: il costo cresce con l'input. Esempio: leggere ogni elemento in una lista una volta. Raddoppia la lista, raddoppia le letture.
- O(N²) — quadratico: il costo cresce come il quadrato dell'input. Esempio: confrontare ogni elemento con ogni altro elemento. Raddoppia N, il lavoro si quadruplica.
Tabella di confronto della crescita:
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
A N=10 la differenza sembra piccola. A N=1.000 il divario diventa enorme.
Confronta O(N) con O(N²)
Usa la tabella di confronto della crescita sopra.
A N=1.000: O(N) richiede 1.000 operazioni. O(N²) richiede 1.000.000 di operazioni.
Come la Struttura del Codice Rivela la Complessità
Come Identificare Big O dal Codice
Big O è nascosto nella forma del tuo codice. Quattro pattern coprono la maggior parte dei casi:
Un singolo ciclo su N elementi: O(N)
# O(N): una singola iterazione attraverso la lista
for item in list_of_n_items:
process(item)Cicli annidati, ognuno su N elementi: O(N²)
# O(N²): ogni elemento accoppiato con ogni altro elemento
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Ricerca in tempo costante: O(1)
Accesso per indice a un array, ricerca in una tabella hash — un passo indipendentemente dalla dimensione.
Divide-and-conquer (taglia il problema a metà ad ogni passo): O(log N)
Ricerca binaria: ogni controllo dimezza gli elementi rimanenti.
---
Big O(N²) nascosto: una lista dentro un ciclo
# Questo sembra O(N) ma è in realtà O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # scansiona tutto visited: O(N)
visited.append(item) # l'intero ciclo: O(N²)La riga if item not in visited scansiona ogni elemento di visited ad ogni iterazione. Una scansione di lista costa O(N). Un ciclo che gira N volte, ognuno facendo O(N) lavoro: O(N) × O(N) = O(N²).
Questo pattern appare in 1.000+ progetti open-source. Il fix richiede un carattere: sostituisci visited = [] con visited = set(). Il test di appartenenza in un set costa O(1), non O(N). Una modifica. Stessi risultati. 1.000× più veloce a N=1.000.
Classifica & Ripara Questo Codice
Leggi questo codice:
result = []
for name in student_names:
if name not in result:
result.append(name)La Teoria Incontra la Pratica
Big O nella Pratica
Big O non è solo teoria. Separa i programmi che finiscono in secondi dai programmi che impiegano 17 minuti — per lo stesso identico compito.
Esempio reale: rilevamento dei cicli di dipendenza in un sistema di build.
Quando installi software, il tuo computer risolve un grafo di dipendenze: il pacchetto A ha bisogno di B, B ha bisogno di C, e così via. Un sistema di build controlla questo grafo per cicli.
Un algoritmo di rilevamento dei cicli O(N²) funziona bene a N=100 pacchetti. A N=50.000 pacchetti (un progetto reale): impiega 17 minuti. Il fix O(N): 10 secondi.
Questo esatto difetto esiste in GHC (compilatore Haskell), pip (gestore pacchetti Python), Maven (sistema build Java), Cargo (gestore pacchetti Rust), & 1.000+ altri progetti.
Non perché i loro autori erano negligenti. visited = [] è stato scritto quando N era piccolo. Il codice si è cristallizzato. N è cresciuto. Nessuno l'ha notato finché il build non ha impiegato mezza ora.
Big O è il vocabolario che ti permette di nominare quello che è successo — & ripararlo.
---
Vuoi approfondire? Il nostro corso unhamming include un capitolo completo su Big O, MOAD-0001 (un vero difetto O(N²) trovato in 1.000+ progetti open-source), & perché nominare un pattern ti permette di trovarlo ovunque. Vedi The Missing Chapter: Algorithmic Complexity.
Prevedi i Tempi di Build
Un sistema di build usa il rilevamento dei cicli O(N²).
Tempi di build misurati:
- N=100 pacchetti: 0,01 secondi
- N=1.000 pacchetti: 1 secondo
Per O(N²): il tempo si ridimensiona come (N_new / N_old)².
Per O(N): il tempo si ridimensiona come (N_new / N_old).