Ogni Classe di Complessità Disegna una Curva
Traccia il Costo Rispetto alla Dimensione dell'Input
Metti la dimensione dell'input N sull'asse x. Metti il costo (operazioni, tempo) sull'asse y. Ogni classe di complessità produce una curva distinta. Puoi riconoscere il tasso di crescita di un algoritmo dalla forma della sua curva di prestazione.
O(1) — linea orizzontale piatta. La funzione f(N) = 1. Nessuna pendenza. Il costo non cambia mai indipendentemente da N. Ricerca in tabella hash: che la tabella contenga 10 o 10.000.000 elementi, un calcolo hash salta direttamente al bucket giusto.
O(log N) — curva verso l'alto dolce, pendenza decrescente. A N = 1.000.000: costo ≈ 20 operazioni. La curva sale ripidamente a piccole N, poi si appiattisce. Ogni raddoppio di N aggiunge esattamente una unità di costo.
O(N) — linea diagonale retta. Pendenza = 1 (nel senso asintotico). Il costo cresce alla stessa velocità di N. Se N triplica, il costo triplica.
O(N log N) — diagonale più ripida con leggera curvatura verso l'alto. Sta sopra O(N) ma sotto O(N²). Il fattore logaritmico aggiunge un moltiplicatore che cresce lentamente alla pendenza lineare.
O(N²) — parabola che si apre verso l'alto. La pendenza aumenta man mano che N cresce. A N = 10: costo = 100. A N = 100: costo = 10.000. A N = 1.000: costo = 1.000.000.
Il Divario che Cresce
Il rapporto O(N²) / O(N) = N. Il divario tra la parabola e la diagonale si allarga man mano che N cresce. A N = 10: divario 10×. A N = 100: divario 100×. A N = 1.000: divario 1.000×. A N = 50.000: divario 50.000×. Il divario è sempre uguale a N.
Calcolo del Divario di Scala
Un grande grafo di dipendenze contiene 50.000 pacchetti (N = 50.000). Un algoritmo viene eseguito in tempo O(N). Un secondo viene eseguito in tempo O(N²). A questo N, il rapporto O(N²)/O(N) = N = 50.000.
Bisezione di un Segmento di Linea
Ricerca Binaria come Bisezione Ripetuta
Un array ordinato di N elementi forma un segmento di linea di lunghezza N. La ricerca binaria divide ripetutamente questo segmento:
1. Punta al punto medio del segmento rimanente.
2. Se target < punto medio: la metà destra scompare. Ricorsione sulla metà sinistra.
3. Se target > punto medio: la metà sinistra scompare. Ricorsione sulla metà destra.
4. Se target = punto medio: fine.
Dopo k bisezioni, il segmento rimanente ha lunghezza N / 2^k. La ricerca termina quando quella lunghezza è uguale a 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Quindi la ricerca binaria su N elementi richiede al massimo log₂N confronti.
Dimezzamento & Raddoppio: Due Lati della Stessa Curva
Dimezzamento e raddoppio sono inversi geometrici. La curva esponenziale 2^k e la curva logaritmica log₂N sono riflessi l'una dell'altra attraverso la linea y = x.
Considera la piegatura della carta: un foglio inizia con uno spessore di 0,1 mm. Ogni piega raddoppia lo spessore. Dopo 42 pieghe: 0,1 mm × 2^42 ≈ 439.804 km — oltre la luna (384.400 km). La ricerca binaria esegue l'inverso: inizia con N elementi, ogni step dimezza il conteggio, raggiunge 1 elemento in log₂N step.
La geometria: la bisezione è un'operazione auto-simile. Ogni bisezione produce due metà che hanno identica struttura al tutto. La ricorsione e i logaritmi condividono questa auto-somiglianza.
Confronti & Raddoppi
Un array ordinato contiene 1.048.576 elementi. Nota: 1.048.576 = 2^20.
Una Funzione Hash come Mappa Geometrica
Funzione Hash come Funzione
Una tabella hash mappa una chiave a un bucket usando una funzione hash:
bucket = hash(key) mod table_size
Questa è una funzione nel senso matematico stretto: mappa un dominio (tutte le possibili chiavi) a un codominio (indici bucket da 0 a table_size − 1). La figura geometrica: le chiavi occupano uno spazio; i bucket occupano un altro. La funzione hash proietta le chiavi negli indici bucket.
O(1) lookup — salto diretto, nessuna ricerca. La funzione hash calcola l'indice bucket in tempo costante. Salta direttamente a quel bucket. Nessuna traversata, nessun loop di confronto.
Fattore di carico. A fattore di carico 0,75, il 75% dei bucket contiene almeno un elemento. Sopra ~0,9, le collisioni aumentano: due chiavi hanno hash nello stesso bucket, formando una catena di elementi dentro quel bucket. La ricerca in una catena lunga degrada a O(N) nel caso peggiore.
Qualità della Distribuzione come Geometria
Una funzione hash ben distribuita diffonde le chiavi uniformemente su tutti i bucket. Geometricamente: il codominio della funzione copre uniformemente il suo codominio. Ogni bucket riceve approssimativamente N / table_size chiavi.
Una funzione hash scadente raggruppa le chiavi in pochi bucket. Geometricamente: il codominio della funzione collassa a un sottoinsieme del codominio — la maggior parte delle chiavi mappa agli stessi pochi punti. I bucket rimanenti rimangono vuoti.
Connessione a MOAD-0001
Sostituire una lista con un set risolve MOAD-0001 perché un set usa internamente una tabella hash. O(N) scansione della lista → O(1) ricerca in tabella hash. Geometricamente: la traversata lineare lungo una sequenza si trasforma in una proiezione diretta tramite una funzione. La sequenza scompare; la funzione la sostituisce.
Analisi di un Hash Scadentemente Distribuito
Una tabella hash ha 1.000 bucket e 900 elementi (fattore di carico 0,9). Una funzione hash scadente invia 500 di quegli elementi nello stesso bucket.