La notazione Big O per principianti: O(1), O(n), O(n al quadrato) e O(log n) spiegate

Crescita, non tempo al cronometro

Il Big O non riguarda quanti secondi impiega qualcosa sul tuo portatile. Riguarda come il lavoro scala quando l'input cresce. Due algoritmi possono essere entrambi O(n), eppure uno gira il doppio più veloce su hardware reale per un fattore costante minore. Il Big O scarta di proposito quella costante, perché con n abbastanza grande la forma della curva di crescita domina qualsiasi moltiplicatore fisso.

La notazione mantiene anche solo il termine che cresce più in fretta. Un algoritmo che fa 3n al quadrato più 5n più 200 operazioni è semplicemente O(n al quadrato), perché quando n è grande il termine al quadrato schiaccia il resto. Ecco perché il Big O è una lente grossolana ma potente: ti dice la classe di comportamento, esattamente ciò che serve nel decidere se una soluzione sopravvivrà a cento volte più dati.

Le quattro classi comuni

O(1) è tempo costante: leggere un elemento di array per indice o controllare una chiave di mappa hash costa lo stesso sforzo che la collezione abbia dieci elementi o dieci milioni. O(log n) è logaritmico: la ricerca binaria dimezza i dati rimanenti a ogni passo, quindi cercare in un elenco ordinato di un miliardo di elementi richiede solo circa trenta confronti. Il dimezzamento è l'immagine speculare del raddoppio che si vede convertendo numeri tra basi.

O(n) è lineare: sommare ogni elemento o scorrere una lista una volta tocca ogni elemento esattamente una volta, quindi il lavoro sale in linea retta con n. O(n al quadrato) è quadratico e di solito viene da cicli annidati, come confrontare ogni coppia di elementi. Con n di 1000 sono un milione di operazioni; con n di 1 000 000 sono mille miliardi, ed è lì che il codice quadratico ingenuo diventa inutilizzabile in silenzio.

Perché la classe che scegli conta

La complessità è ciò che separa un prototipo che funziona sul tuo file di test da un software che sopravvive ai dati di produzione. Ordinare con un algoritmo O(n al quadrato) sembra istantaneo su cento righe e si blocca su un milione. Passare a un ordinamento O(n log n) tiene la stessa attività sotto il secondo. L'algoritmo che scegli, non la velocità della macchina, fissa il tetto di quanti dati puoi gestire.

Detto ciò, il Big O è asintotico: descrive il comportamento quando n tende all'infinito. Per input piccoli, una routine più semplice O(n al quadrato) può battere una sofisticata O(n log n) con molto overhead. La regola pratica è conoscere la classe di ogni operazione centrale e poi ottimizzare le parti che vedranno davvero un n grande, invece di inseguire costanti in codice che tratta solo input minuscoli.

Domande frequenti

Un Big O più basso è sempre più veloce?

Non per input piccoli. Il Big O ignora i fattori costanti, quindi un metodo O(n log n) con molta preparazione può perdere contro un semplice ciclo O(n al quadrato) quando n è minuscolo. La classe più bassa vince quando l'input è abbastanza grande.

Qual è la differenza tra O(log n) e O(n log n)?

O(log n) fa un solo passaggio logaritmico, come una singola ricerca binaria. O(n log n) svolge una quantità logaritmica di lavoro per ciascuno degli n elementi, che è il costo di algoritmi di ordinamento efficienti come il merge sort.

Il Big O copre anche la memoria?

Sì. La stessa notazione descrive la complessità in spazio, quanta memoria extra serve a un algoritmo al crescere di n. Un ordinamento sul posto può usare O(1) di spazio extra, mentre uno che copia i dati usa O(n).

Perché ignoriamo le costanti e i termini inferiori?

Perché con n grande il termine che cresce più in fretta domina tutto il resto, e le costanti dipendono da hardware che non controlli. Scartarli dà un confronto portabile di come gli algoritmi scalano, indipendente da qualsiasi macchina.