Notazione asintotica: O, Ω, Θ spiegate senza simboli inutili

Perché si contano le operazioni, non i secondi

Due algoritmi che ordinano mille numeri possono finire nello stesso istante e comportarsi in modo opposto con dieci milioni. Il cronometro non lo mostra, per due ragioni: dipende dalla macchina, dal linguaggio e da quello che sta girando in quel momento, e misura una sola taglia alla volta. Jeff Erickson, nel suo testo ad accesso aperto, parte da qui con un esempio volutamente ridicolo, il tempo per cantare una filastrocca di n strofe: chi canta più veloce o più lento cambia la costante, ma raddoppiare n raddoppia comunque il tempo, ed è questa la crescita «asintotica» Θ(n). La sua indicazione pratica è contare quante volte l'algoritmo esegue una certa istruzione.

La notazione asintotica serve a dire come cresce il costo di un algoritmo all'aumentare della dimensione dell'input, non quanto è veloce su cento elementi. Per questo in tutto l'articolo i programmi contano confronti, che sono gli stessi su qualunque computer, e riportano il rapporto fra il conteggio e la crescita dichiarata. Gli unici tempi dell'articolo sono quelli ipotetici della tabella finale, dichiarati tali.

Le definizioni, lette dalla fonte

Prendo le definizioni dal capitolo sulle notazioni asintotiche di Mathematics for Computer Science (Lehman, Leighton, Meyer, MIT, testo aperto, § 14.7), perché sono scritte con precisione e senza il linguaggio vago delle dispense. Tutte parlano di funzioni f e g dei naturali (o dei reali) in sé, non di algoritmi: l'algoritmo entra solo quando decidi quale funzione di costo chiamare f.

• O (limite superiore). f = O(g) se esistono una costante c > 0 e un n₀ tali che per ogni n ≥ n₀ vale |f(n)| ≤ c · g(n). La funzione f non cresce più in fretta di g, a meno di una costante.
• Ω (limite inferiore). f = Ω(g) se g = O(f): f cresce almeno quanto g, a meno di una costante.
• Θ (limite stretto). f = Θ(g) se valgono entrambe, f = O(g) e g = O(f): f e g sono uguali a meno di un fattore costante.
• o piccolo (strettamente più lenta). f = o(g) se il limite di f(n)/g(n) per n che tende all'infinito è 0. Allora f cresce in modo sostanzialmente più lento di g, ed è un'affermazione più forte di O.

Le prime tre sono relazioni di grandezza fra funzioni, con una costante di tolleranza; la quarta toglie la tolleranza e chiede che il rapporto sparisca. Se scambi l'ordine di O e Ω il senso si rovescia, ed è l'errore più comune: «almeno O(n²)» non ha significato, perché O fornisce solo limiti superiori; per un limite inferiore si scrive Ω(n²). Lo stesso testo avverte che O(g) non è un numero e che il segno «=» è una convenzione storica: da 2n = O(n) non segue O(n) = 2n.

Il listato seguente prova le definizioni su casi piccoli. La funzione primo_controesempio cerca, tra n₀ e un massimo, il primo n per cui la disuguaglianza della definizione fallisce. È un controllo finito e non dimostra niente: la dimostrazione di 3n² + 2n + 7 ≤ 4n² per n ≥ 4 è algebra (equivale a n² − 2n − 7 ≥ 0, vera da n ≥ 1 + √8 ≈ 3,83). Il programma serve a trovare gli errori di chi sceglie c e n₀ a occhio.

# Cerca un controesempio alla disuguaglianza della definizione di O, in un intervallo finito.
# Attenzione: una verifica finita NON dimostra nulla, trova solo eventuali errori.
def primo_controesempio(f, g, c, n0, n_max):
    for n in range(n0, n_max + 1):
        if f(n) > c * g(n):
            return n
    return None

f = lambda n: 3 * n**2 + 2 * n + 7

print("f(n)=3n^2+2n+7 contro g(n)=n^2")
print("  c=4, n0=4 :", primo_controesempio(f, lambda n: n**2, 4, 4, 10**6))
print("  c=4, n0=3 :", primo_controesempio(f, lambda n: n**2, 4, 3, 10**6))
print("  c=3, n0=1 :", primo_controesempio(f, lambda n: n**2, 3, 1, 10**6))

print("100n contro n^2 (c=1)")
print("  n0=1  :", primo_controesempio(lambda n: 100 * n, lambda n: n**2, 1, 1, 1000))
print("  n0=100:", primo_controesempio(lambda n: 100 * n, lambda n: n**2, 1, 100, 1000))

print("4^n contro 2^n: rapporto f/g")
for n in (10, 20, 30):
    print(f"  n={n}: {4**n // 2**n}")

print("1000*n^1.9 diviso n^2 (limite 0, ma lentissimo)")
for esp in (3, 6, 12, 30):
    n = 10**esp
    print(f"  n=10^{esp}: {1000 * n**-0.1:.2f}")

# Output (due esecuzioni, uscita identica):
# f(n)=3n^2+2n+7 contro g(n)=n^2
#   c=4, n0=4 : None
#   c=4, n0=3 : 3
#   c=3, n0=1 : 1
# 100n contro n^2 (c=1)
#   n0=1  : 1
#   n0=100: None
# 4^n contro 2^n: rapporto f/g
#   n=10: 1024
#   n=20: 1048576
#   n=30: 1073741824
# 1000*n^1.9 diviso n^2 (limite 0, ma lentissimo)
#   n=10^3: 501.19
#   n=10^6: 251.19
#   n=10^12: 63.10
#   n=10^30: 1.00

Le tre prime righe di uscita mostrano che i due testimoni sono davvero una coppia: con c = 4 e n₀ = 4 non c'è controesempio, ma abbassando n₀ a 3 la disuguaglianza salta proprio in n = 3, dove 3·9 + 6 + 7 = 40 supera 4·9 = 36, e con c = 3 salta subito. Lo stesso 100n è sotto n² solo da n = 100: sotto quella soglia vince il termine con la costante grande. Il rapporto 4ⁿ / 2ⁿ è 2ⁿ e non resta limitato, quindi 4ⁿ non è O(2ⁿ), nonostante 4 sia «solo una costante» più grande di 2: è la «trappola dell'esponenziale» che il testo di Lehman e colleghi descrive. Infine 1000·n^1,9 è o(n²), il rapporto tende a zero, ma il listato mostra che a n = 10¹² vale ancora 63 e raggiunge 1 solo a n = 10³⁰: «da un certo punto in poi» può voler dire un punto lontanissimo.

Un limite non è un caso: la confusione più diffusa

Nelle dispense si legge spesso «Big-O è il caso peggiore, Omega è il caso migliore». È sbagliato, e la ragione è nelle definizioni appena viste: O, Ω e Θ sono relazioni fra due funzioni, non nomi di casi. Il «caso» è un'altra scelta, a monte: dato un algoritmo e una taglia n, gli input possibili sono tanti e il costo cambia da uno all'altro, quindi devi decidere quale funzione di n stai descrivendo. Le scelte comuni sono tre: il costo sul peggior input di taglia n, T_peggiore(n); quello sul migliore, T_migliore(n); la media su una distribuzione di input dichiarata, T_medio(n). Soltanto dopo scegli un limite per quella funzione, e ciascuna delle tre può ricevere un O, un Ω e un Θ.

La ricerca lineare è il caso più semplice. Il programma conta quante volte confronta il valore cercato con un elemento: se il valore è in prima posizione i confronti sono 1, se è in ultima sono n. Ho usato una piccola classe che incrementa un contatore in __eq__, così il numero è esatto e non dipende dal computer. Nella stessa prova guardo cosa succede con l'operatore in su una lista e su un set: la tentazione di dire che «le liste di Python sono O(1)» nasce dall'accesso per indice, che è un'altra operazione.

# Contiamo i confronti di uguaglianza, non i secondi.
class Chiave:
    confronti = 0
    def __init__(self, v):
        self.v = v
    def __hash__(self):
        return hash(self.v)
    def __eq__(self, altro):
        Chiave.confronti += 1
        return self.v == altro.v

def conta(contenitore, valore):
    Chiave.confronti = 0
    valore in contenitore
    return Chiave.confronti

print(f"{'n':>9} {'lista (ultimo)':>15} {'lista (primo)':>14} {'set':>4}  confronti/n")
for n in (1_000, 10_000, 100_000):
    lista = [Chiave(i) for i in range(n)]
    insieme = set(lista)
    ultimo = conta(lista, Chiave(n - 1))
    primo = conta(lista, Chiave(0))
    set_ = conta(insieme, Chiave(n - 1))
    print(f"{n:>9} {ultimo:>15} {primo:>14} {set_:>4}  {ultimo / n:.3f}")

# Output (due esecuzioni, uscita identica):
#         n  lista (ultimo)  lista (primo)  set  confronti/n
#      1000            1000              1    1  1.000
#     10000           10000              1    1  1.000
#    100000          100000              1    1  1.000

Il conteggio sulla lista cresce esattamente come n, quindi il rapporto con n resta 1,000 a ogni taglia: nel caso peggiore la ricerca di un valore in lista è Θ(n), e nel caso migliore (primo elemento) costa 1 confronto, cioè Θ(1). Per il set il conteggio è 1 a ogni taglia, perché il valore viene trovato calcolando l'hash e confrontando con un solo candidato. La tabella di complessità della documentazione ufficiale di Python indica x in l come O(n) e x in s come O(1), con la precisazione che i costi dei dizionari (e dei set) sono tempi del caso medio: se tutte le chiavi hanno lo stesso hash, ogni operazione costa O(n). Una struttura che «dà O(1)» lo dà sotto un'ipotesi sui dati, e va detta.

L'ordinamento per inserimento mostra la stessa cosa in forma più netta, perché i due casi sono lontani. Il listato conta i confronti su un input già ordinato e su uno in ordine inverso, e li affianca alla formula n(n−1)/2.

# Una stessa funzione di costo, tre input diversi della stessa taglia n.
def insertion_confronti(a):
    a = list(a); c = 0
    for i in range(1, len(a)):
        k = a[i]; j = i - 1
        while j >= 0:
            c += 1
            if a[j] > k:
                a[j + 1] = a[j]; j -= 1
            else:
                break
        a[j + 1] = k
    return c

print(f"{'n':>6} {'ordinato':>9} {'inverso':>10} {'n(n-1)/2':>10}")
for n in (100, 200, 400, 800):
    ordinato = insertion_confronti(range(n))
    inverso = insertion_confronti(range(n, 0, -1))
    print(f"{n:>6} {ordinato:>9} {inverso:>10} {n * (n - 1) // 2:>10}")

# Output (due esecuzioni, uscita identica):
#      n  ordinato    inverso   n(n-1)/2
#    100        99       4950       4950
#    200       199      19900      19900
#    400       399      79800      79800
#    800       799     319600     319600

Sull'input ordinato i confronti sono n−1; su quello inverso sono esattamente n(n−1)/2, come indica l'ultima colonna. Quindi T_migliore(n) = Θ(n) e T_peggiore(n) = Θ(n²). Detto del «tempo dell'algoritmo» senza specificare, l'unica cosa vera per ogni input è che il costo sta fra Ω(n) e O(n²): non esiste un Θ unico, perché la funzione di costo non è unica. Ne segue che «Ω è il caso migliore» è falso come lo è «O è il caso peggiore»: per la ricerca lineare T_migliore(n) è O(1), quindi un O descrive benissimo anche il caso migliore, e T_peggiore(n) è Ω(n), quindi anche un Ω può descrivere il caso peggiore.

Quick sort e merge sort: tre funzioni, due algoritmi

Il quick sort rende evidente perché serve dichiarare la funzione. Con il pivot scelto come primo elemento, la funzione del caso peggiore e quella del caso medio hanno ordini diversi. Si può dire onestamente: T_peggiore(n) = Θ(n²) (input già ordinato, partizioni sbilanciatissime) e T_medio(n) = Θ(n log n) se la media è presa su tutte le permutazioni equiprobabili. Quindi «il quick sort è O(n²)» è vero (è il limite superiore del caso peggiore, e vale quindi per ogni caso), mentre «è Θ(n log n)» non ha senso senza dire quale caso.

Il programma conta i confronti elemento-pivot del quick sort su input ordinato e su permutazioni casuali, con venti semi fissi per ogni taglia e la media riportata. Come controllo indipendente, la colonna formula è il valore atteso in forma chiusa 2(n+1)H_n − 4n, con H_n numero armonico. Per il merge sort ho contato i confronti nella fusione su input ordinato e su una permutazione casuale.

import math, random

def quicksort_confronti(dati):
    """Pivot = primo elemento. Conta i confronti elemento-pivot."""
    c = 0
    pila = [list(dati)]
    while pila:
        a = pila.pop()
        if len(a) <= 1:
            continue
        p = a[0]
        c += len(a) - 1
        pila.append([x for x in a[1:] if x < p])
        pila.append([x for x in a[1:] if x >= p])
    return c

def merge_confronti(a):
    if len(a) <= 1:
        return list(a), 0
    m = len(a) // 2
    s, cs = merge_confronti(a[:m]); d, cd = merge_confronti(a[m:])
    out, i, j, c = [], 0, 0, 0
    while i < len(s) and j < len(d):
        c += 1
        if s[i] <= d[j]:
            out.append(s[i]); i += 1
        else:
            out.append(d[j]); j += 1
    out += s[i:] + d[j:]
    return out, cs + cd + c

def attesi_quicksort(n):  # formula chiusa del caso medio: 2(n+1)H_n - 4n
    return 2 * (n + 1) * sum(1 / k for k in range(1, n + 1)) - 4 * n

print("quicksort, pivot = primo elemento")
print(f"{'n':>6} {'ordinato':>10} {'/n^2':>6} {'casuale':>9} {'formula':>9} {'/(n log2 n)':>12}")
for n in (500, 1000, 2000, 4000):
    ordinato = quicksort_confronti(range(n))
    prove = []
    for seme in range(20):
        r = random.Random(seme); d = list(range(n)); r.shuffle(d)
        prove.append(quicksort_confronti(d))
    media = sum(prove) / len(prove)
    print(f"{n:>6} {ordinato:>10} {ordinato / n**2:>6.3f} {media:>9.0f} {attesi_quicksort(n):>9.0f} {media / (n * math.log2(n)):>12.3f}")

print("merge sort")
print(f"{'n':>6} {'ordinato':>9} {'casuale':>9} {'n log2 n':>9} {'ord/(n log2 n)':>15} {'cas/(n log2 n)':>15}")
for n in (500, 1000, 2000, 4000):
    _, o = merge_confronti(list(range(n)))
    r = random.Random(1); d = list(range(n)); r.shuffle(d)
    _, c = merge_confronti(d)
    nl = n * math.log2(n)
    print(f"{n:>6} {o:>9} {c:>9} {nl:>9.0f} {o / nl:>15.3f} {c / nl:>15.3f}")

# Output (due esecuzioni, uscita identica):
# quicksort, pivot = primo elemento
#      n   ordinato   /n^2   casuale   formula  /(n log2 n)
#    500     124750  0.499      4810      4806        1.073
#   1000     499500  0.499     10957     10986        1.099
#   2000    1999000  0.500     24164     24730        1.102
#   4000    7998000  0.500     54646     54989        1.142
# merge sort
#      n  ordinato   casuale  n log2 n  ord/(n log2 n)  cas/(n log2 n)
#    500      2216      3849      4483           0.494           0.859
#   1000      4932      8705      9966           0.495           0.873
#   2000     10864     19362     21932           0.495           0.883
#   4000     23728     42792     47863           0.496           0.894

Sul quick sort con input ordinato, il rapporto fra confronti e n² è 0,499-0,500: per n = 4000 i confronti sono 7.998.000, cioè esattamente n(n−1)/2. La media su input casuale (4.810 per n = 500) segue la formula chiusa entro il 2,3% (lo scarto massimo, a n = 2000): stessa curva, quindi il campione di venti semi è ragionevole. Il rapporto con n·log₂n sale lentamente (1,073 → 1,142) perché il coefficiente asintotico è 2 ln 2 ≈ 1,386 e c'è un termine −n che pesa meno al crescere di n: per Θ(n log n) basta che il rapporto resti dentro due costanti, e lo è. Quanto al merge sort, il rapporto con n·log₂n è 0,49-0,50 sull'input ordinato e 0,86-0,89 su quello casuale: in entrambi i casi sta fra due costanti, quindi T(n) = Θ(n log n) in tutti i casi. È il vero significato di «ha una caratterizzazione Θ ben definita». Ho contato confronti, non tempo: il tempo dipende anche da allocazioni e spostamenti, che qui non sono misurati.

Quando in un articolo divulgativo leggi «il quick sort è O(n log n)», quella frase sottintende il caso medio o un pivot scelto in modo casuale, e va letta così: con il pivot sul primo elemento il caso peggiore resta quadratico, come mostra la colonna dell'input ordinato.

Un limite inferiore su un problema: l'ordinamento per confronti

Ω è il linguaggio giusto per dire che non si può fare meglio di un certo ordine, e lo si dice del problema, non di un algoritmo. Il risultato classico è che ogni algoritmo di ordinamento che usa solo confronti, nel caso peggiore, esegue Ω(n log n) confronti. La traccia della dimostrazione standard (la riporto per intero, non l'ho copiata da una fonte) è questa: gli input possibili sono le n! permutazioni, ogni confronto ha due esiti e quindi dimezza al più il numero di permutazioni ancora compatibili, e per distinguerle tutte servono almeno ⌈log₂(n!)⌉ confronti nel caso peggiore. Poiché n! ≥ (n/2)^(n/2), vale log₂(n!) ≥ (n/2)·log₂(n/2), che è Ω(n log n).

La prova numerica enumera tutte le permutazioni per n da 2 a 8, conta i confronti del merge sort su ciascuna e prende il massimo, da affiancare al limite teorico.

import itertools, math

def merge_confronti(a):
    if len(a) <= 1:
        return list(a), 0
    m = len(a) // 2
    s, cs = merge_confronti(a[:m]); d, cd = merge_confronti(a[m:])
    out, i, j, c = [], 0, 0, 0
    while i < len(s) and j < len(d):
        c += 1
        if s[i] <= d[j]:
            out.append(s[i]); i += 1
        else:
            out.append(d[j]); j += 1
    out += s[i:] + d[j:]
    return out, cs + cd + c


print(f"{'n':>2} {'ceil(log2 n!)':>14} {'merge, caso peggiore':>21}")
for n in range(2, 9):
    peggiore = max(merge_confronti(list(p))[1] for p in itertools.permutations(range(n)))
    print(f"{n:>2} {math.ceil(math.log2(math.factorial(n))):>14} {peggiore:>21}")

# Output (due esecuzioni, uscita identica):
#  n  ceil(log2 n!)  merge, caso peggiore
#  2              1                     1
#  3              3                     3
#  4              5                     5
#  5              7                     8
#  6             10                    11
#  7             13                    14
#  8             16                    17

Per n da 2 a 4 il merge sort raggiunge il limite teorico (1, 3, 5), per n da 5 a 8 supera il minimo di un confronto, perché la fusione non è ottimale per piccole taglie: il limite inferiore non è mai violato, come deve essere, e il merge sort non lo supera di molto. Ricorda anche che il «Ω(n log n)» vale solo per gli algoritmi che usano esclusivamente confronti; ordinamenti che sfruttano il valore delle chiavi, come il counting sort, non sono coperti dal teorema.

Le costanti contano, e la notazione le nasconde

La notazione asintotica nasconde le costanti per costruzione: 100n è Θ(n) e n² è Θ(n²), ma il primo listato ha già mostrato che 100n è sotto n² solo da n = 100 in poi. Un algoritmo asintoticamente peggiore può quindi essere migliore su dati piccoli, e la pratica lo conferma: la documentazione di sviluppo di CPython sull'ordinamento delle liste (listsort.txt) spiega che il Timsort estende i segmenti ordinati troppo corti con un insertion sort binario, e che quando l'array è più corto di una soglia lo ordina interamente così. Lì si legge che i test su dati casuali hanno trovato valori equivalenti di minrun fra 16 e 128, e la scelta è caduta su 32. Non ho misurato i tempi su questa macchina per un confronto fra insertion e merge: il numero di confronti, da solo, non rivela il punto di incrocio, che dipende dal costo di ogni passo.

La lezione è che l'analisi asintotica è una guida sul comportamento al crescere dell'input, non un giudizio sul tempo di una singola chiamata. Se i tuoi dati hanno dimensioni fisse e piccole, misura. Lo stesso testo di Lehman e colleghi fa l'esempio dell'algoritmo di moltiplicazione di matrici con O(n^2,55) operazioni, quasi mai usato perché conviene solo su matrici di taglia impraticabile.

Le classi più comuni e che cosa significano a n = un milione

Dal più lento a crescere al più veloce a esplodere, queste sono le classi che incontrerai più spesso. Gli ordini di grandezza sono calcolati supponendo che ogni operazione costi 1 nanosecondo: è un'ipotesi di lavoro per rendere visibili le differenze, non una misura di una macchina reale. Il listato calcola la colonna di destra.

import math

n = 10**6
SECONDI_ANNO = 365.25 * 24 * 3600
print("n = 10^6, un'operazione = 1 ns (ipotesi di lavoro, non una misura)")
righe = [("log n", math.log2(n)), ("n", n), ("n log n", n * math.log2(n)), ("n^2", n**2), ("n^3", n**3)]
for nome, ops in righe:
    secondi = ops * 1e-9
    if secondi < 1e-3:
        t = f"{secondi * 1e9:.4g} ns"
    elif secondi < 1:
        t = f"{secondi * 1e3:.4g} ms"
    elif secondi < 86400 * 365:
        t = f"{secondi / 60:.4g} min"
    else:
        t = f"{secondi / SECONDI_ANNO:.4g} anni"
    print(f"  {nome:>8}: {ops:.4g} operazioni -> {t}")
log10_ops = n * math.log10(2)
print(f"  {'2^n':>8}: 10^{log10_ops:.0f} operazioni -> 10^{log10_ops - 9 - math.log10(SECONDI_ANNO):.0f} anni")

# Output (due esecuzioni, uscita identica):
# n = 10^6, un'operazione = 1 ns (ipotesi di lavoro, non una misura)
#      log n: 19.93 operazioni -> 19.93 ns
#          n: 1e+06 operazioni -> 1 ms
#    n log n: 1.993e+07 operazioni -> 19.93 ms
#        n^2: 1e+12 operazioni -> 16.67 min
#        n^3: 1e+18 operazioni -> 31.69 anni
#        2^n: 10^301030 operazioni -> 10^301013 anni

La riga che pesa è la distanza fra O(n log n) e O(n²) alla stessa taglia: venti millisecondi contro diciassette minuti. Con la stessa ipotesi, il salto da O(n³) a O(2ⁿ) non è più confrontabile con niente di fisico: un numero di anni con trecentomila cifre non è «lungo», è fuori da qualunque scala fisica. Questo spiega perché la distinzione fra polinomiale ed esponenziale conta più di qualunque costante, mentre fra due algoritmi della stessa classe le costanti tornano a essere il criterio.

Cosa sai fare adesso

Sai leggere O, Ω, Θ e o come relazioni fra funzioni con la loro definizione, e sai verificare un testimone (c, n₀) che ti viene proposto. Soprattutto sai evitare i tre scivoloni di cui sopra, che compaiono ovunque: dire «Big-O è il caso peggiore», dire «Omega è il caso migliore», dire che un algoritmo è «Θ(...)» senza dire di quale caso. Il metodo che ti porti via è semplice: per ogni affermazione sul costo, scrivi prima la funzione (quale algoritmo, quale caso, quale operazione contata), poi il limite, poi conta su qualche taglia e controlla che il rapporto resti dentro una costante.

• Big-O: limite superiore di una funzione di costo; si può applicare al caso peggiore, a quello migliore o a quello medio.
• Omega Ω: limite inferiore; per i problemi dice «non si può fare meglio», per gli algoritmi dice «non costa meno di».
• Theta Θ: limite stretto di una funzione di costo precisa; non esiste per «l'algoritmo» se i casi hanno ordini diversi.
• Le costanti contano sui dati piccoli: la notazione guida, il conteggio e la misura decidono.

Le quattro voci sono il promemoria da tenere accanto a ogni stima di complessità che leggi o scrivi, e ciascuna previene un errore diverso: confondere il limite con il caso, pretendere un Θ dove i casi divergono, dimenticare l'ipotesi dietro un O(1), fidarsi della classe quando i dati sono piccoli. Nello stesso filone, la serie «Algoritmi e Strutture Dati» continua con l'analisi della complessità (articolo 01), gli algoritmi di ordinamento e la ricerca lineare, binaria e con hash table.