Complessità degli algoritmi e notazione O-grande

Le lezioni del primo semestre sono partite a metà settembre (al Politecnico di Milano il 14 settembre 2026), e in Fondamenti di informatica o in Algoritmi e strutture dati uno dei primi argomenti “veri” — dopo il ripasso di programmazione — è la complessità computazionale e la notazione O-grande. Dove il calendario prevede una prova in itinere, questa cade tipicamente a fine ottobre-inizio novembre (al Politecnico dal 29 ottobre al 2 novembre 2026, quindi circa cinque settimane da qui); la sessione invernale, negli atenei con calendario anticipato come il Politecnico, parte il 7 gennaio 2027.

È un argomento che sembra “solo teoria” e invece si esamina soprattutto con esercizi: analizzare un frammento di codice e dire qual è la sua complessità, dimostrare una relazione con la definizione formale, risolvere una ricorrenza. Qui trovi il metodo per farlo senza tirare a indovinare.

Cosa significa davvero “complessità”

La complessità di un algoritmo è una funzione che descrive come cresce il costo (tempo o memoria) al crescere della dimensione dell’input, che chiamiamo $n$. Non è il tempo in secondi — quello dipende dal processore, dal linguaggio, da chi altro sta usando la macchina — è un modo di descrivere la crescita che prescinde da tutto questo.

Ha senso distinguere tre casi:

• Caso peggiore (worst case): l’input che fa fare all’algoritmo il massimo lavoro possibile. È quello su cui si basa quasi sempre l’analisi d’esame, perché dà una garanzia valida sempre.
• Caso migliore (best case): l’input più favorevole.
• Caso medio (average case): il costo medio su tutti gli input possibili, pesati per probabilità. Più difficile da calcolare, meno richiesto nei primi esami.

Le definizioni formali: O, Ω, Θ

La notazione O-grande dà un limite superiore alla crescita di una funzione. Si dice che $f(n)=O(g(n))$ se esistono una costante $c>0$ e un valore $n_0$ tali che:

In parole: da un certo punto in poi ($n\ge n_0$), $f(n)$ non supera mai $g(n)$ a meno di una costante moltiplicativa. La costante $c$ e la soglia $n_0$ sono proprio i due ingredienti che un esercizio “dimostra $f(n)=O(g(n))$” ti chiede di esibire esplicitamente — non basta dire “è vero”, va costruita la coppia $(c,n_0)$ che lo rende vero.

Le altre due notazioni completano il quadro:

$\Omega$ è il limite inferiore (l’opposto di $O$), $\Theta$ è il caso in cui $f(n)$ è delimitata sia sopra sia sotto dallo stesso $g(n)$: la crescita è “esattamente quella”, non solo “al massimo quella”. Un errore concettuale frequente è usare $O$ e $\Theta$ come sinonimi: dire che un algoritmo è $\Theta (n^2)$ è un’affermazione più forte che dire che è $O(n^2)$, perché esclude anche che possa crescere più lentamente.

Regole pratiche per calcolare la complessità

Nella maggior parte degli esercizi non serve applicare la definizione formale ogni volta: bastano poche regole meccaniche.

1. Tieni solo il termine dominante, e butta via le costanti. $3n^2+5n+20$ è $O(n^2)$: per $n$ grande il termine $n^2$ domina su tutto il resto, e le costanti moltiplicative ($3$, $5$, $20$) non cambiano l’ordine di crescita.
2. Istruzioni in sequenza si sommano, ma vince il termine peggiore. Un ciclo $O(n)$ seguito da un ciclo $O(n^2)$ costa $O(n+n^2)=O(n^2)$.
3. Cicli annidati indipendenti si moltiplicano. Due cicli for annidati, ciascuno da $0$ a $n$, danno $O(n)\cdot O(n)=O(n^2)$.
4. Cicli annidati dipendenti vanno sommati, non moltiplicati “a occhio”. Se il ciclo interno dipende dall’indice di quello esterno (per esempio il ciclo interno va da $0$ a $i$), il numero totale di iterazioni è una somma, non un semplice prodotto — vedi il prossimo paragrafo.
5. Un indice che raddoppia (o dimezza) a ogni iterazione dà una crescita logaritmica. Un ciclo for (int i = 1; i < n; i = i * 2) gira circa ${\log }_{2}n$ volte, perché ci vogliono ${\log }_{2}n$ raddoppi per passare da $1$ a $n$.

Il caso dei cicli annidati dipendenti: la somma di Gauss

Questo esercizio compare spessissimo e viene sbagliato quasi sempre nello stesso modo:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        // operazione O(1)
    }
}

L’errore comune è concludere “due cicli annidati, quindi $O(n^2)$” senza verificare che il conto torni davvero. In questo caso il numero totale di iterazioni del ciclo interno, su tutte le iterazioni di quello esterno, è:

che è comunque $O(n^2)$ — la conclusione finale è giusta — ma per la ragione sbagliata se ci si arriva “a occhio” invece che sommando. Vale la pena saper scrivere questo passaggio esplicitamente, perché con cicli dipendenti in modo diverso (per esempio il ciclo interno che va da $0$ a $\sqrt{i}$) la scorciatoia “annidati quindi moltiplico” dà proprio il risultato sbagliato, mentre la somma esplicita no.

La gerarchia delle complessità

Ordinare le funzioni di crescita più comuni, dalla più lenta alla più veloce, è qualcosa che conviene avere automatico:

Per farsi un’idea concreta di cosa significhi in pratica, ecco una tabella con $n=20$ e $n=50$ (valori arrotondati):

Il salto fra $n^2$ e $2^n$ è quello che, in pratica, decide se un algoritmo è utilizzabile su input grandi o no: un algoritmo $O(2^n)$ diventa impraticabile molto prima di quanto l’intuizione suggerisca, perché ogni singolo elemento in più dell’input raddoppia il lavoro, non lo aumenta di una quantità fissa.

Ricerca lineare, ricerca binaria, e gli algoritmi di ordinamento

Due algoritmi di ricerca che tornano in ogni esame:

• Ricerca lineare: scorre l’array elemento per elemento finché non trova il target (o finisce l’array). Caso peggiore $O(n)$: nessuna ipotesi sull’ordine dei dati.
• Ricerca binaria: richiede un array ordinato, e a ogni passo dimezza lo spazio di ricerca confrontando il target con l’elemento centrale. Caso peggiore $O(\log n)$.

E tre algoritmi di ordinamento classici, con la complessità del caso peggiore che ogni esame vuole sapere a memoria:

• Bubble sort: confronta e scambia elementi adiacenti, $O(n^2)$.
• Insertion sort: inserisce ogni elemento nella posizione corretta rispetto alla parte già ordinata, $O(n^2)$ nel caso peggiore (ma quasi $O(n)$ se l’array è già quasi ordinato — un dettaglio che i professori amano chiedere).
• Merge sort: divide l’array a metà ricorsivamente, ordina le metà, poi le fonde (merge). $O(n\log n)$, sempre — anche nel caso peggiore, ed è proprio questo il motivo per cui è preferito ai primi due su input grandi.

Ricorrenze: il metodo dell’albero

Molti algoritmi ricorsivi hanno un costo descritto da un’equazione di ricorrenza. Le due che compaiono più spesso:

Ricerca binaria: $T(n)=T(n/2)+c$ — un solo sotto-problema di metà dimensione, più un costo costante $c$ per il confronto.

Merge sort: $T(n)=2T(n/2)+cn$ — due sotto-problemi di metà dimensione, più un costo $cn$ per la fase di merge.

Il metodo dell’albero rende visibile da dove viene la soluzione: si disegna un albero in cui ogni nodo è una chiamata, con il costo proprio di quella chiamata (escludendo le chiamate figlie) scritto accanto.

Per il merge sort: al livello $0$ c’è un nodo con costo $cn$; al livello $1$ ci sono $2$ nodi, ciascuno con costo $c(n/2)$, quindi il livello costa ancora $cn$ in totale; al livello $2$ ci sono $4$ nodi da $c(n/4)$, di nuovo $cn$ in totale. Ogni livello costa $cn$, e ci sono ${\log }_{2}n$ livelli (perché $n$ si dimezza a ogni livello finché non arriva a $1$):

Per la ricerca binaria il ragionamento è più semplice: un solo nodo per livello, costo costante $c$ per nodo, e ${\log }_{2}n$ livelli:

Il teorema master formalizza questo metodo per ricorrenze della forma $T(n)=aT(n/b)+f(n)$, dando la soluzione in base al confronto fra $f(n)$ e $n^{{\log }_{b}a}$ senza dover ridisegnare l’albero ogni volta — utile da conoscere, ma capire perché funziona il metodo dell’albero resta il modo più solido per non sbagliare quando il professore cambia leggermente i numeri della ricorrenza rispetto all’esempio visto a lezione.

Gli errori che costano punti

1. Confondere $O$ con “il tempo esatto”. $O(n^2)$ non vuol dire “impiega esattamente $n^2$ passi”: vuol dire che, da un certo punto in poi, non supera $c\cdot n^2$ per qualche costante $c$. Un algoritmo che fa esattamente $n^2/2$ operazioni è comunque, correttamente, $O(n^2)$.
2. Contare male cicli annidati dipendenti trattandoli come se fossero indipendenti, invece di sommare esplicitamente (vedi la somma di Gauss sopra). A volte il risultato finale coincide comunque, a volte no: il metodo sbagliato prima o poi tradisce.
3. Dimenticare le costanti quando servono davvero, cioè proprio nelle dimostrazioni con $c$ e $n_0$ espliciti: lì le costanti non si buttano via, sono l’oggetto della dimostrazione.

Tre esercizi svolti

Esercizio 1 — analizzare tre frammenti di codice.

// (a)
for (int i = 0; i < n; i++) {
    std::cout << i;
}
// Complessità: O(n) — un ciclo, n iterazioni.

// (b)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        std::cout << i << j;
    }
}
// Complessità: O(n^2) — due cicli indipendenti, n * n iterazioni.

// (c)
for (int i = 1; i < n; i = i * 2) {
    std::cout << i;
}
// Complessità: O(log n) — l'indice raddoppia a ogni passo.

Esercizio 2 — dimostrare che $3n^2+5n=O(n^2)$.

Bisogna trovare $c$ e $n_0$ tali che $3n^2+5n\le c\cdot n^2$ per ogni $n\ge n_0$. Per $n\ge 1$ vale $5n\le 5n^2$, quindi:

Basta scegliere $c=8$ e $n_0=1$: per ogni $n\ge 1$, $3n^2+5n\le 8n^2$. La dimostrazione è completa non appena si esibiscono $c$ e $n_0$ e si verifica la disuguaglianza — non serve trovare la coppia “più stretta possibile”, ne basta una che funzioni.

Esercizio 3 — risolvere la ricorrenza $T(n)=2T(n/2)+n$, con $T(1)=1$.

Con il metodo dell’albero: livello $0$ costa $n$; livello $1$ ha $2$ nodi da $n/2$ ciascuno, quindi ancora $n$ in totale; livello $k$ costa sempre $n$ in totale, e ci sono ${\log }_{2}n$ livelli prima di arrivare ai casi base. Quindi:

È la stessa struttura del merge sort visto sopra — non a caso: la ricorrenza del merge sort è esattamente questa, a meno della costante moltiplicativa sul termine lineare.

Dove porta dopo

Una volta solida la complessità asintotica, il passo successivo tipico del corso sono le strutture dati (liste, alberi, heap, grafi) e come la loro scelta cambia la complessità delle operazioni — un buon punto di raccordo, se il tuo corso lo prevede insieme, è anche basi di dati e SQL, dove indici e query plan sono un’applicazione diretta di questi stessi concetti. Se il corso lavora in C e ti manca ancora sicurezza su puntatori e memoria dinamica, questa guida ai puntatori copre esattamente quel terreno. E se vieni da un percorso tecnico delle superiori dove hai già visto cicli e array, il post su cicli annidati e array in terza informatica mostra la stessa logica un livello più sotto — utile per capire da dove arrivi, non per prepararti all’esame universitario in sé.

Come lavoro su questo argomento in lezione

Con chi si blocca sulla complessità, il problema quasi mai è la definizione in sé: è non avere ancora tradotto in pratica cosa vuol dire “trovare $c$ e $n_0$”, oppure fidarsi troppo dell’intuizione sui cicli annidati senza verificarla con una somma esplicita come quella di Gauss. Lavoriamo su frammenti di codice veri — spesso quelli dell’esercizio d’esame che ti ha bloccato — e li analizziamo insieme riga per riga, prima di passare alle dimostrazioni formali.

Se ti stai preparando anche su calcolo numerico, la logica di stimare un errore con costanti esplicite è la stessa identica di questa dimostrazione con $c$ e $n_0$ — vale la pena vederle insieme.

Le lezioni di informatica per studenti universitari sono online e uno a uno; trovi il quadro generale delle ripetizioni universitarie sulla pagina dedicata. Se vuoi parlarne prima di prenotare, siamo su /contatti/.