Cos'è la complessità computazionale (Big O)

Due programmi possono risolvere lo stesso problema, ma uno impiega un millisecondo e l'altro dieci minuti. Come fai a sapere in anticipo quale codice "scalerà" bene quando i dati diventano tanti? La risposta è la notazione Big O.

In questo articolo ti spiego cos'è la complessità computazionale e la notazione Big O in modo semplice, con esempi di codice che ti fanno vedere la differenza.

Cos'è la complessità computazionale in parole semplici

La notazione Big O è un modo per descrivere come cresce il tempo (o la memoria) richiesto da un algoritmo all'aumentare della dimensione dei dati in ingresso, ignorando i dettagli e concentrandosi sull'andamento generale. In breve, ti dice se un algoritmo "regge" quando i dati esplodono.

Non misura i secondi esatti, che dipendono dal computer, ma il modo in cui il costo cresce. Un algoritmo O(n) raddoppia il lavoro se raddoppi i dati; uno O(n²) lo quadruplica.

Perché ti interessa

Con pochi dati quasi tutto funziona velocemente. Il problema arriva quando passi da 100 a un milione di elementi: lì la differenza tra un algoritmo efficiente e uno scadente diventa abissale. Capire il Big O ti aiuta a scrivere codice che non rallenta quando l'applicazione cresce.

Le complessità più comuni

O(1) – tempo costante

Il tempo non dipende dalla quantità di dati. Accedere a un elemento di una lista per indice è O(1).

def primo_elemento(lista):
    return lista[0]   # sempre un'operazione, sempre veloce

O(n) – tempo lineare

Il tempo cresce in proporzione ai dati. Scorrere tutta una lista una volta è O(n).

def somma(lista):
    totale = 0
    for x in lista:   # tocco ogni elemento una volta
        totale += x
    return totale

Se raddoppi gli elementi, raddoppia il lavoro.

O(n²) – tempo quadratico

Tipico dei cicli annidati: per ogni elemento scorri di nuovo tutta la lista.

def coppie(lista):
    for a in lista:
        for b in lista:    # ciclo dentro un ciclo
            print(a, b)

Con 1.000 elementi fai un milione di operazioni. Da evitare sui grandi dataset.

O(log n) – tempo logaritmico

Cresce molto lentamente. È il caso della ricerca binaria, che a ogni passo dimezza lo spazio di ricerca. Cercare in un milione di elementi richiede appena una ventina di passi.

Una scala di riferimento

Dalla più veloce alla più lenta, ecco l'ordine tipico:

• O(1): ottimo, costante.
• O(log n): molto buono.
• O(n): accettabile, lineare.
• O(n log n): tipico dei buoni algoritmi di ordinamento.
• O(n²): pesante, da evitare sui grandi numeri.

Big O e le strutture dati

La complessità dipende molto dalla struttura dati che scegli. Cercare un valore in una lista è O(n), ma in un dizionario è O(1). Per questo, capire le strutture dati e la complessità va a braccetto: scegliere il contenitore giusto può trasformare un algoritmo lento in uno velocissimo.

Anche la ricorsione può nascondere costi enormi: la versione ingenua di Fibonacci è esponenziale, O(2ⁿ), e diventa inutilizzabile già con numeri non troppo grandi.

Non ossessionarti (all'inizio)

Un consiglio onesto: se stai imparando a programmare da zero, non bloccarti sulla complessità fin dal primo giorno. Prima scrivi codice che funziona, poi impari a renderlo efficiente. Il Big O diventa importante quando lavori con molti dati o ti prepari per i colloqui tecnici.

In sintesi

La notazione Big O descrive come cresce il costo di un algoritmo all'aumentare dei dati. Conoscere O(1), O(n) e O(n²) ti basta per riconoscere subito il codice che scala bene e quello che ti metterà nei guai. È uno strumento di intuizione più che di calcolo preciso.

Vuoi imparare ad analizzare e migliorare i tuoi algoritmi con esempi pratici? Trovi percorsi guidati nei corsi di CodeGrind.