Notazione Big O — Complessità temporale spiegata in modo semplice

La notazione Big O ti dice quanto velocemente possono crescere il tempo di esecuzione o l’uso di memoria di un algoritmo quando aumenta la dimensione dell’input. Se ti chiedi: “Che cosa succede quando il problema diventa molto più grande?”, Big O è il modo standard per rispondere.

Per questo si dice che la ricerca lineare è $O(n)$ e la ricerca binaria è $O(\log n)$. L’obiettivo non è prevedere i millisecondi esatti su una singola macchina. L’obiettivo è confrontare gli andamenti di crescita.

Che cosa significa Big O

Se un algoritmo impiega tempo $T(n)$ su un input di dimensione $n$, allora

$$T(n) = O(f(n))$$

significa che esistono costanti $C > 0$ e $n_0$ tali che

$$T(n) \le C f(n) \quad \text{per ogni } n \ge n_0$$

Questo vuol dire che Big O è un’affermazione di maggiorazione sulla crescita per input sufficientemente grandi.

In parole semplici: una volta che $n$ è abbastanza grande, il tempo di esecuzione non cresce più velocemente di un multiplo costante di $f(n)$.

Perché Big O è utile

Big O fornisce un modo indipendente dalla macchina per confrontare gli algoritmi. Un programma può essere più veloce su un portatile che su un altro, ma la tendenza di crescita resta comunque importante.

Questa tendenza conta soprattutto quando la dimensione dell’input cambia molto. Un algoritmo che va bene per $100$ elementi può diventare impraticabile per $10^6$ elementi se il suo tasso di crescita è sfavorevole.

Le complessità temporali più comuni a colpo d’occhio

• $O(1)$: il lavoro resta limitato mentre $n$ cresce.
• $O(\log n)$: il lavoro cresce lentamente, spesso quando la dimensione del problema viene ridotta ripetutamente.
• $O(n)$: il lavoro cresce più o meno in proporzione alla dimensione dell’input.
• $O(n \log n)$: leggermente più di lineare, comune negli algoritmi di ordinamento efficienti.
• $O(n^2)$: il lavoro cresce come il quadrato della dimensione dell’input, spesso a causa di cicli annidati sugli stessi dati.

Queste etichette confrontano la crescita, non la velocità esatta. Un algoritmo $O(n)$ può comunque essere più lento di uno $O(n^2)$ per input piccoli se i suoi fattori costanti sono grandi.

Esempio svolto: perché la ricerca lineare è $O(n)$

Supponi di scorrere una lista da sinistra a destra cercando un valore obiettivo. Nel caso peggiore, il valore non c’è oppure si trova proprio alla fine, quindi potresti dover controllare ogni elemento una volta.

Se la lista ha $n$ elementi, il numero di controlli può essere al massimo $n$. Per questo il tempo nel caso peggiore è

$$O(n)$$

L’idea utile da ricordare è semplice: se la dimensione della lista raddoppia, anche il numero massimo di controlli può raddoppiare circa. È proprio questo schema che Big O descrive.

Che cosa Big O non considera

Big O ignora intenzionalmente i fattori costanti e i termini di ordine inferiore quando confronta la crescita per input grandi.

Per esempio, se

$$T(n) = 3n + 2$$

allora $T(n)$ è comunque $O(n)$. La costante $3$ e il termine aggiuntivo $2$ contano per il tempo esatto, ma non cambiano l’andamento principale della crescita.

Questo non significa che le costanti non contino mai nella pratica. Significa che Big O risponde a una domanda più specifica: come scala il costo quando $n$ diventa grande.

Errori comuni con Big O

Errore 1: trattare Big O come tempo di esecuzione esatto

$O(n)$ non significa che il tempo di esecuzione sia esattamente di $n$ passaggi. Significa che la crescita è limitata superiormente da un multiplo costante di $n$ quando $n$ è abbastanza grande.

Errore 2: dimenticare la condizione per grandi valori di $n$

La definizione formale deve valere solo per tutti gli $n \ge n_0$. Big O riguarda il comportamento asintotico, non ogni input molto piccolo.

Errore 3: supporre che Big O indichi sempre il tempo tipico

Nelle discussioni sugli algoritmi, Big O descrive spesso il tempo nel caso peggiore, ma questa è una convenzione legata al contesto. La complessità media e quella nel caso migliore sono questioni diverse e dovrebbero essere indicate chiaramente.

Errore 4: confrontare gli algoritmi solo con Big O

Big O è importante, ma nei sistemi reali possono contare molto anche l’uso di memoria, il costo di implementazione e i fattori costanti.

Dove si incontra la notazione Big O

Big O compare in informatica, matematica discreta e analisi delle prestazioni. È particolarmente utile quando si confrontano algoritmi di ricerca, ordinamento, attraversamento di grafi e programmazione dinamica.

Più in generale, si usa ogni volta che ti interessa capire come scala un processo, invece di osservare solo come si comporta a una dimensione fissa.

Prova un esempio simile

Prendi un semplice doppio ciclo che attraversa una griglia $n \times n$. Conta quante volte viene eseguita l’azione interna. Se il lavoro totale cresce come $n^2$, hai un esempio concreto del perché cicli ripetuti sugli stessi dati portano spesso a un comportamento $O(n^2)$.