Tassi di Crescita, Non Costi Assolute
Big O: Misurare Come Cresce il Costo del Lavoro
La notazione di Big O misura il tasso di crescita del costo dell'algoritmo - non il costo assoluto.
La domanda a cui Big O risponde: quando la dimensione dell'input N si raddoppia, il lavoro si raddoppia? Si quadruplica? Rimane piano?
La 'O' sta per 'ordine di grandezza'. L'espressione all'interno delle 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. Sia l'array ha 10 elementi che 10 milioni, una ricerca unica rimane una ricerca unica.
- O(N) — lineare: il costo cresce con l'input. Esempio: leggere ogni elemento in una lista una volta. Doppia la lista, doppia le letture.
- O(N²) — quadratica: il costo cresce come il quadrato dell'input. Esempio: confrontare ogni elemento con ogni altro elemento. Doppia N, quadruplica il lavoro.
Tavola di confronto del 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 tavola di confronto del crescita sopra.
A N=1,000: O(N) richiede 1,000 operazioni. O(N²) richiede 1,000,000 operazioni.
Come la struttura del codice rivela la complessità
Come identificare Big O dal codice
Big O si nasconde nella forma del tuo codice. Quattro schemi coprono la maggior parte dei casi:
Boucle singola su N elementi: O(N)
# O(N): un passaggio attraverso la lista
for item in list_of_n_items:
process(item)Boucle annidate, ognuna su N elementi: O(N²)
# O(N²): ogni elemento viene 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 costante: O(1)
Accesso all'indice dell'array, ricerca in un dizionario hash - un passo indipendentemente dalla dimensione.
Divide et impera (taglia il problema a metà passo dopo passo): O(log N)
Ricerca binaria: ogni controllo riduce a metà gli elementi rimanenti.
---
O(N²) nascosto: una lista all'interno di una boucle
# Questo sembra O(N) ma è effettivamente O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # scansione di tutti gli elementi di visited: O(N)
visited.append(item) # il ciclo intero: O(N²)La linea 'if item not in visited' scorre ogni elemento di 'visited' ad ogni iterazione. Una scansione di una lista costa O(N). Un ciclo che esegue N volte, ognuna con O(N) lavoro: O(N) × O(N) = O(N²).
Questo schema compare in oltre 1.000 progetti open source. La soluzione richiede un solo carattere: sostituire 'visited = []' con 'visited = set()'. La verifica dell'appartenenza a un set costa O(1), non O(N). Un cambiamento. Stessi risultati. 1.000× più veloce a N=1.000.
Classifica e correggi questo codice
Leggi questo codice:
result = []
for name in student_names:
if name not in result:
result.append(name)Teoria e Pratica
Big O nel Vivo
Big O non è solo teoria. Separazione tra programmi che si completano in secondi e programmi che richiedono 17 minuti - sullo stesso compito esatto.
Esempio reale: la detezione di cicli di dipendenza in un sistema di build.
Quando installi software, il tuo computer risolve un grafo delle dipendenze: package A ha bisogno di B, B ha bisogno di C, e così via. Un sistema di build controlla questo grafo per i cicli.
Un algoritmo di ciclo-detection O(N²) va bene a N=100 pacchetti. A N=50,000 pacchetti (un progetto reale): richiede 17 minuti. La soluzione O(N): 10 secondi.
Questo stesso difetto esiste in GHC (compilatore Haskell), pip (gestore pacchetti Python), Maven (sistema di build Java), Cargo (gestore pacchetti Rust) e in oltre 1.000 altri progetti.
Non perché i suoi autori fossero negligenti. visited = [] è stato scritto quando N era piccolo. Il codice si è calcificato. N è cresciuto. Nessuno si è accorto fino a quando il build non ha richiesto mezz'ora.
Big O è la lingua che ti permette di nominare cosa è successo - e correggerlo.
---
Vuoi andare più in profondità? Il nostro corso non Hamming include un intero capitolo su Big O, MOAD-0001 (un vero difetto O(N²) trovato in oltre 1.000 progetti open-source) e perché nominare un pattern ti permette di trovarlo ovunque. Vedi [Il capitolo mancante: la complessità algoritmica](/it/un/unhamming_algorithmic_complexity).
Pronostica i Tempi di Build
Un sistema di build utilizza la detezione di 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 proporziona come (N_new / N_old)².
Per O(N): il tempo si proporziona come (N_new / N_old).