Notazione Big O Spiegata con Esempi di Codice

Una lookup su un dizionario Python impiega circa 100 nanosecondi, che il dizionario contenga 1.000 chiavi o 1.000.000. Un doppio ciclo che cerca duplicati in una lista impiega mezzo millisecondo su 200 elementi e 136 millisecondi su 3.200. Sedici volte l’input, quasi 280 volte l’attesa. Stessa macchina, stesso Python. La notazione Big O è il nome di quella differenza.

Cosa misura la notazione Big O

Big O descrive come cresce il tempo di esecuzione (o l’uso di memoria) di un pezzo di codice all’aumentare dell’input. Non è una lettura al cronometro e non le importa se il tuo portatile è veloce o lento. Le interessa la forma della curva di crescita: raddoppiando l’input, il tempo raddoppia, quadruplica, o si muove appena?

La notazione elimina tutto ciò che non cambia quella forma, dai fattori costanti all’hardware su cui gira il codice. O(n) significa “proporzionale a n”, che il costo reale sia 3n + 7 oppure 0.001n + 1000000. Rendi n abbastanza grande e resta solo la forma.

Esempi di Big O in Python, cronometrati a input crescenti

Ogni funzione qui sotto è stata cronometrata con il modulo timeit di Python su Python 3.11, a dimensioni di input distanti un ordine di grandezza (o un raddoppio) l’una dall’altra.

Tempo costante: una lookup su dizionario

1
2

def dict_lookup(d, key):
    return d[key]

L’input cresce di mille volte. Il tempo per chiamata resta piatto, dentro il rumore di misurazione. Un dizionario è una tabella hash: Python calcola l’hash della chiave e salta dritto al bucket corrispondente, indipendentemente da quante altre voci esistano. Questo è O(1), tempo costante.

Tempo lineare: sommare una lista

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Ogni decuplicazione di n porta un aumento di tempo di circa dieci volte. Il ciclo tocca ogni elemento esattamente una volta, quindi il lavoro scala direttamente con l’input. Questo è O(n), tempo lineare, ed è dove vive la maggior parte del codice di tutti i giorni.

Tempo quadratico: cercare duplicati nel modo ingenuo

1
2
3
4
5
6

def has_duplicate_naive(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Raddoppiare n quadruplica più o meno il tempo a ogni passo. Il ciclo esterno gira n volte e quello interno gira quasi n volte per ogni iterazione esterna, quindi il lavoro totale è proporzionale a n * n. Questo è O(n^2), tempo quadratico. È la classe che rovina il codice in produzione, perché sembra a posto in un test con 50 righe e va in timeout con 50.000.

Tempo logaritmico: ricerca binaria

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Un aumento di mille volte di n fa appena raddoppiare il tempo. Ogni passo del ciclo scarta metà dell’intervallo rimanente, quindi il numero di passi necessari cresce con log2(n) invece che con n: circa 10 passi per mille elementi, circa 20 per un milione. Questo è O(log n). Git bisect esegue lo stesso algoritmo sulla cronologia dei commit invece che su un array ordinato: trova il commit che ha rotto tutto tra centinaia di candidati in una manciata di passi, perché ogni test scarta metà dell’intervallo rimanente.

Tempo linearitmico: ordinare

1

sorted_nums = sorted(nums)

Ogni passo decuplo di n costa più del decuplo in tempo, ma ben lontano dal centuplo che mostrerebbe un algoritmo quadratico. Il sorted() di Python usa Timsort, che esegue O(n log n) confronti: il merge procede in circa log n round, e ogni round tocca ciascuno degli n elementi una volta per unire le sequenze adiacenti. Ogni ordinamento general-purpose che userai nella pratica quotidiana (Timsort, mergesort, il caso medio di quicksort) finisce qui, ed è per questo che O(n log n) viene considerato “il massimo che un ordinamento possa offrire” invece di essere confrontato con O(n).

Le classi di complessità Big O più comuni, dalla più veloce alla più lenta

Guarda le ultime due righe. Passare da O(n log n) a O(n^2) con un milione di elementi è la differenza tra un report che gira in un secondo e uno ancora in esecuzione quando qualcuno uccide il processo.

Cosa non dice la notazione Big O

Big O descrive la crescita asintotica, cioè cosa succede quando n diventa arbitrariamente grande. Tre cose cadono in quel vuoto.

Le costanti sono invisibili. Un O(n) con un fattore costante di 1000 può essere più lento in pratica di un O(n^2) con una costante minuscola, per qualsiasi n che vedrai mai. Big O ti dice quale curva vince alla fine, non quale funzione è più veloce sui tuoi dati. È per questo che l’insertion sort, benché O(n^2), resta la scelta migliore per array molto piccoli: lo stesso Timsort usa un insertion sort binario per costruire ogni piccola run fino a una lunghezza minima (minrun, tipicamente 32-64 elementi) prima di iniziare a unire le run tra loro.

Un n piccolo non mostra la curva. I tempi quadratici qui sopra sono diventati evidentemente quadratici solo quando n ha superato qualche centinaio. A n = 10 praticamente tutto finisce prima che tu te ne accorga, ed è per questo che una funzione può superare ogni test che scrivi in locale e poi crollare sui volumi di dati di produzione.

La complessità spaziale è un asse a parte. dict_lookup, sum_loop, has_duplicate_naive e binary_search girano tutte usando una memoria extra pressoché costante: nessuna alloca una seconda struttura dati proporzionale all’input. sorted() no: restituisce una nuova lista della stessa dimensione dell’input, O(n) di spazio, perché non ordina mai sul posto. Alcuni algoritmi scambiano memoria per velocità di proposito: una funzione di Fibonacci con memoization salva ogni risultato già calcolato, spendendo O(n) di spazio per trasformare O(2^n) di tempo in O(n). Quando dichiari la complessità di una funzione, specifica a quale asse ti riferisci: la versione più veloce è spesso quella che usa più memoria.

Come individuare un O(n^2) nascosto nel tuo codice

Il doppio ciclo di prima è il caso ovvio. Quello che arriva in produzione di solito non ha nessun ciclo annidato in vista.

Test di appartenenza dentro un ciclo. x in qualche_lista è O(n) su una lista, perché Python deve scansionarla tutta. Eseguire quel controllo dentro un ciclo che già gira n volte ti dà O(n^2) senza un secondo for in vista:

1
2
3
4
5
6

# O(n^2): "in" scansiona l'intera lista a ogni iterazione
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Sostituisci la lista con un set, dove l’appartenenza è O(1), e il ciclo scende a O(n):

1
2
3
4
5
6

# O(n): "in" è una lookup hash
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Ricostruire una lista invece di aggiungerci elementi. result + [item] alloca una nuova lista e copia dentro ogni elemento già esistente; result.append(item) fa crescere la lista esistente sul posto.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # copia tutto quello costruito finora, ogni volta
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) ammortizzato
    return result

Costruire una lista di 8.000 elementi con + ha impiegato 65 ms. La stessa lista con .append() ha impiegato 0,15 ms. Il divario si allarga al crescere di n, perché uno è quadratico e l’altro è lineare.

La query N+1. Recuperi una lista di righe, poi ci giri sopra con un ciclo che lancia un’altra query per riga per i dati correlati, e una singola query è diventata n + 1: O(n) andirivieni verso il database invece di uno solo. Un indice, come visto in come funzionano gli indici database, trasforma una singola lookup da una scansione O(n) della tabella a O(log n). Non fa nulla per un ciclo che manda mille query separate. La correzione ha la stessa forma di quella del set qui sopra: sostituisci l’operazione per riga con un’operazione fatta una sola volta. Qui significa una singola query con un join, che i tipi di JOIN in SQL spiegati con esempi illustra nel dettaglio.

Come misurare la complessità del tuo codice

Scegli la funzione che sospetti, di solito una con un ciclo il cui numero di iterazioni dipende dalla dimensione dei dati. Cronometrala con timeit a tre o quattro dimensioni di input, ciascuna dieci volte la precedente, e dividi ogni tempo per quello precedente. Un rapporto vicino a 1 è O(1) o O(log n). Vicino a 10 è lineare. Tra 10 e 100 è O(n log n), come il 17-21 della tabella di sorted(). Vicino a 100 significa che hai un O(n^2) da stanare; se questo rende le dimensioni grandi troppo lente da aspettare, raddoppia n invece di moltiplicarlo per dieci e cerca un rapporto vicino a 4. Comincia dai test di appartenenza su liste e dalle ricostruzioni con + dentro quel ciclo, poi qualsiasi query mandata una volta per riga.

Articoli correlati

• Git Bisect: Trovare il Commit che ha Introdotto un Bug
• Come Funzionano gli Indici Database e Quando Usarli
• Tipi di JOIN in SQL Spiegati con Esempi