Algoritmi Che Terminano In Tempo: Un Controllo Big O

Scrivi una funzione, la esegui sui dati di test e funziona bene. Poi arriva ai dati di produzione — 500.000 righe invece di 500 — e la richiesta scade. Succede costantemente, ed è quasi sempre un problema di complessità nascosto dietro codice che sembrò ragionevole a piccola scala.

Perché il tuo laptop ti ha mentito

Un algoritmo O(n²) eseguito su 100 elementi fa 10.000 operazioni. È istantaneo su qualsiasi macchina. Esegui lo stesso algoritmo su 100.000 elementi e sei a 10 miliardi di operazioni — minuti o ore invece di millisecondi. Il salto da n a n² non sembra pericoloso finché n non diventa grande, ed è esattamente per questo che passa la revisione del codice e i test locali.

Un esempio classico: controllare i duplicati con un ciclo annidato.

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

Questo è O(n²). Sostituiscilo con un set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Ora è O(n). Le ricerche nei set sono in media O(1), quindi l'intera funzione scala linearmente invece che quadraticamente. Su 10.000 elementi è la differenza tra circa 100 milioni di confronti e 10.000.

Misura prima di ottimizzare

Non indovinare. Usa timeit per microbenchmark:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Per funzioni più grandi, profila con cProfile:

python -m cProfile -s cumulative myscript.py

Guarda la colonna cumtime. Se una funzione consuma il 90% del tempo di esecuzione, è il tuo obiettivo. Ottimizzare codice che non è il collo di bottiglia spreca il tuo tempo e aggiunge complessità senza vantaggi.

Modelli comuni che diventano lenti in silenzio

Controlli ripetuti di appartenenza a una lista. if x in my_list è O(n) per una lista ma O(1) in media per un set o dict. Se stai controllando l'appartenenza dentro un ciclo, quel controllo O(n) dentro un ciclo O(n) ti dà O(n²) complessivo. Sostituisci la lista con un set e sei di nuovo a O(n).

Concatenazione di stringhe in un ciclo. In Python, result += chunk dentro un ciclo su stringhe è O(n²) nel caso peggiore perché le stringhe sono immutabili e ogni concatenazione copia il tutto. Usa ''.join(chunks) invece — costruisce la stringa una volta.

Ordinamento quando non serve. sorted() è O(n log n). Se la stai chiamando dentro un ciclo solo per trovare il massimo o il minimo ad ogni iterazione, usa max()/min() (O(n)) o meglio, un heap (heapq) se hai bisogno dell'estremo corrente ripetutamente. heapq.nlargest(k, data) è O(n log k), molto più economico che ordinare l'intera lista quando k è piccolo.

Funzioni ricorsive senza memoizzazione. Fibonacci ricorsivo ingenuo è O(2ⁿ) perché ricalcola gli stessi sottoproblemi ripetutamente. Aggiungi functools.lru_cache e scende a O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Leggere Big O dal codice reale, velocemente

Conta i cicli annidati sullo stesso input — quello è di solito il tuo esponente. Un singolo ciclo è O(n). Un ciclo dentro un ciclo è O(n²) a meno che l'intervallo del ciclo interno non si riduca (come nella forma ottimizzata di bubble sort, ancora O(n²) nel caso peggiore ma meno confronti). Chiamate ricorsive che dividono il problema a metà, come binary search o merge sort, puntano a O(log n) o O(n log n). Chiamate ricorsive che si dividono in molteplici chiamate per livello, come Fibonacci ingenuo, puntano a tempo esponenziale — un segnale forte che hai bisogno di memoizzazione o di una riscrittura iterativa.

Una buona abitudine: prima di scrivere cicli annidati o ricorsione su dati rivolti all'utente, chiediti quale potrebbe essere realisticamente n in produzione, non nel tuo file di test. Se n potrebbe raggiungere sei cifre, una soluzione O(n²) ha bisogno di una seconda occhiata prima di essere spedita.

Per ulteriori informazioni sull'analisi di complessità, algoritmi di ordinamento e strumenti di profiling, consulta i segmenti Python e Computer Science su Korra Studio.