Hai una funzione che con cento elementi risponde all'istante e con un milione ti fa aspettare mezz'ora, mentre una sua gemella, scritta in modo apparentemente identico, regge entrambe le dimensioni. Il cronometro ti dice che una è più lenta, non perché, e soprattutto non ti dice che cosa succederà con dieci milioni di elementi. La notazione Big-O serve a questo: è un'affermazione su come cresce il numero di operazioni quando cresce l'ingresso, e si può controllare contando le operazioni invece di guardare l'orologio. In questo articolo la usi, la smonti e la verifichi su programmi veri.
È il primo articolo della serie Algoritmi e Strutture Dati, quindi non servono prerequisiti oltre a saper leggere un ciclo. Tutti i listati sono in Python 3.14 con la sola libreria standard e si eseguono con python3 -I; le uscite riportate sono quelle ottenute eseguendoli, due volte con risultato identico. Le complessità non sono dichiarate: sono contate, e dove un risultato è una formula ne ho fatto un secondo calcolo indipendente.
Che cosa afferma davvero O, Ω e Θ
Dire che f(n) = O(g(n)) significa che esistono due costanti, c > 0 e n₀, tali che f(n) ≤ c·g(n) per ogni n ≥ n₀. Le due costanti sono i «testimoni» dell'affermazione: senza di loro la frase non dice nulla, e con loro la frase si può smentire con un solo controesempio. Prendi f(n) = 3n² + 10n + 7, un costo plausibile per una funzione con un doppio ciclo, un ciclo semplice e qualche istruzione fissa. Il listato propone c = 4 e n₀ = 11 e li mette alla prova in tre modi.
# Big-O come affermazione verificabile: f(n) = 3n^2 + 10n + 7 e' O(n^2)?
def f(n):
return 3 * n * n + 10 * n + 7
c, n0 = 4, 11 # i due "testimoni" della definizione: f(n) <= c * n^2 per ogni n >= n0
# 1) verifica numerica su un intervallo ampio (non e' una dimostrazione)
assert all(f(n) <= c * n * n for n in range(n0, 20001))
print("f(n) <= 4n^2 per ogni n da", n0, "a 20000: vero")
# 2) il testimone n0 non e' arbitrario: un passo prima la disuguaglianza fallisce
print("n = 10:", f(10), "<=", c * 10 * 10, "->", f(10) <= c * 100)
# 3) controllo indipendente, per via algebrica: f(n) <= 4n^2 <=> n^2 - 10n - 7 >= 0
g = lambda n: n * n - 10 * n - 7
first_ok = next(n for n in range(1, 100) if g(n) >= 0)
print("primo n con n^2 - 10n - 7 >= 0:", first_ok)
# 4) la cota inferiore: f(n) >= 3n^2 per ogni n >= 1, quindi f e' anche Omega(n^2) => Theta(n^2)
assert all(f(n) >= 3 * n * n for n in range(1, 20001))
print("f(n) >= 3n^2 per ogni n da 1 a 20000: vero")
# Output:
# f(n) <= 4n^2 per ogni n da 11 a 20000: vero
# n = 10: 407 <= 400 -> False
# primo n con n^2 - 10n - 7 >= 0: 11
# f(n) >= 3n^2 per ogni n da 1 a 20000: veroIl primo controllo percorre l'intervallo da 11 a 20.000 e non è una dimostrazione: è la tagliola che scatta se i testimoni sono sbagliati. Il secondo mostra che n₀ non è decorativo, perché a n = 10 la disuguaglianza fallisce (407 contro 400). Il terzo è il calcolo indipendente: f(n) ≤ 4n² equivale a n² − 10n − 7 ≥ 0, e il primo intero che lo soddisfa è proprio 11. Infine la cota inferiore f(n) ≥ 3n² vale da n = 1, e i due limiti insieme danno Θ(n²).
Le tre notazioni si leggono come tre domande diverse sulla stessa funzione.
- O (limite superiore): il costo non cresce più in fretta di g, a meno di una costante.
- Ω (limite inferiore): il costo non cresce più lentamente di g, a meno di una costante.
- Θ (limite stretto): valgono entrambe, quindi g descrive la crescita senza margine.
La distinzione conta più di quanto sembri, perché «è O(n²)» è vero anche per un algoritmo che costa n: è un limite, non una descrizione. Quando in un colloquio o in una revisione di codice qualcuno dice «è O(n²)», la domanda utile è se intende Θ o soltanto un limite largo. Per i testi di riferimento sulla definizione formale e sulle sue conseguenze il manuale classico è Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, quarta edizione, MIT Press 2022 (citato, non letto per questo articolo: la pagina dell'editore ha risposto 403 al mio client).
Migliore, peggiore e medio: tre numeri diversi per lo stesso codice
La stessa funzione ha un costo diverso a seconda dell'ingresso, e per questo si parla di caso migliore, peggiore e medio. Nella ricerca lineare il caso migliore è trovare l'elemento in prima posizione, il peggiore è non trovarlo mai, e il medio dipende da un'ipotesi: qui ogni posizione è equiprobabile. Il listato conta i confronti, non i secondi, e per il caso medio fa la media esatta su tutte le posizioni possibili invece di campionare.
# Tre scenari della ricerca lineare, misurati CONTANDO i confronti (non i secondi)
def linear_search(arr, target):
comparisons = 0
for i, x in enumerate(arr):
comparisons += 1
if x == target:
return i, comparisons
return -1, comparisons
print(f"{'n':>6} {'migliore':>9} {'peggiore (assente)':>19} {'medio (presente)':>17} {'(n+1)/2':>9}")
for n in (10, 100, 1000, 10000):
arr = list(range(n))
best = linear_search(arr, arr[0])[1]
worst = linear_search(arr, -1)[1]
# media esatta su TUTTE le posizioni possibili, ciascuna con la stessa probabilita'
mean = sum(linear_search(arr, t)[1] for t in arr) / n
print(f"{n:>6} {best:>9} {worst:>19} {mean:>17.1f} {(n + 1) / 2:>9.1f}")
# Output:
# n migliore peggiore (assente) medio (presente) (n+1)/2
# 10 1 10 5.5 5.5
# 100 1 100 50.5 50.5
# 1000 1 1000 500.5 500.5
# 10000 1 10000 5000.5 5000.5La colonna del caso medio coincide con (n + 1)/2 fino al decimale: la media dei numeri da 1 a n è proprio quella. Il caso peggiore costa n confronti e il migliore uno solo, quindi l'intervallo è enorme e la scelta del numero da citare non è un dettaglio. Per un servizio con un obiettivo di latenza sul 99° percentile conta il peggiore; per un lavoro batch che gira sull'intero archivio conta la media. Se non sai quale dei due ti riguarda, hai scoperto che ti manca un'informazione sul carico, non sull'algoritmo.
Le classi di crescita come conteggi
Le classi che incontrerai ovunque sono poche, e si riconoscono dalla forma dei cicli.
- O(1): un numero fisso di passi, come leggere
a[k]in una lista. - O(log n): a ogni passo l'ingresso si dimezza, come nella ricerca binaria.
- O(n): un passaggio su tutti gli elementi.
- O(n log n): un passaggio per ogni livello di dimezzamento, come negli ordinamenti efficienti.
- O(n²): due cicli annidati sullo stesso ingresso.
La lista è ordinata per crescita, e l'ordine è la sostanza: ciascuna classe, per n abbastanza grande, supera tutte le precedenti. Per vederlo con i numeri, il listato implementa un esempio per classe con un contatore e li esegue su n = 64, 128, … 4096. Poi calcola la pendenza sul piano log-log: se raddoppiando n le operazioni si moltiplicano per 2p, la pendenza è p.
# Le classi di crescita come CONTEGGI di operazioni elementari, su n = 2^k
import math
def count_linear(n): # un ciclo: n passi
ops = 0
for _ in range(n):
ops += 1
return ops
def count_quadratic(n): # due cicli annidati: n^2 passi
ops = 0
for _ in range(n):
for _ in range(n):
ops += 1
return ops
def count_log(n): # dimezzamento: floor(log2 n) + 1 passi
ops = 0
while n >= 1:
n //= 2
ops += 1
return ops
def count_nlogn(n): # ciclo esterno n, interno con dimezzamento
return sum(count_log(n) for _ in range(n))
sizes = [2 ** k for k in range(6, 13)] # 64 ... 4096
funcs = [("log", count_log), ("lineare", count_linear),
("n log n", count_nlogn), ("quadratica", count_quadratic)]
rows = {name: [fn(n) for n in sizes] for name, fn in funcs}
print("n ", *[f"{name:>11}" for name, _ in funcs])
for i, n in enumerate(sizes):
print(f"{n:<7}", *[f"{rows[name][i]:>11}" for name, _ in funcs])
# pendenza sul piano log-log tra l'ultima coppia di dimensioni: raddoppiare n moltiplica le operazioni per 2^pendenza
print("\npendenza log-log tra n=2048 e n=4096")
for name, _ in funcs:
slope = math.log2(rows[name][-1] / rows[name][-2])
print(f" {name:<11} {slope:.3f}")
# Output:
# n log lineare n log n quadratica
# 64 7 64 448 4096
# 128 8 128 1024 16384
# 256 9 256 2304 65536
# 512 10 512 5120 262144
# 1024 11 1024 11264 1048576
# 2048 12 2048 24576 4194304
# 4096 13 4096 53248 16777216
#
# pendenza log-log tra n=2048 e n=4096
# log 0.115
# lineare 1.000
# n log n 1.115
# quadratica 2.000Leggi la tabella per colonne: il logaritmo passa da 7 a 13 mentre n si moltiplica per 64, il lineare e il quadratico seguono la forma attesa. La pendenza dice la stessa cosa in un solo numero: 1,000 per il lineare, 2,000 per il quadratico, 0,115 per il logaritmo e 1,115 per n log n. Quest'ultimo valore è il motivo per cui un grafico log-log di un algoritmo n log n sembra «quasi lineare ma un po' storto»: la pendenza vale 1 + 1/log₂ n, e tende a 1 lentamente.
Un'aritmetica che si cita spesso, e che qui è solo aritmetica: se una macchina eseguisse 10⁹ operazioni semplici al secondo (un'ipotesi, non una misura), un algoritmo da n² = 10¹² operazioni con n = 10⁶ impiegherebbe 1.000 secondi, circa 16 minuti, mentre uno da circa 2·10⁷ ne impiegherebbe 0,02. La differenza non è «veloce contro lento» ma «possibile contro impossibile», e dipende solo dal conteggio.
Quando «O(2ⁿ)» è una scorciatoia sbagliata
Molti testi dicono che il Fibonacci ricorsivo ingenuo è O(2ⁿ). Come limite superiore è vero, ma come descrizione è sbagliato, e il conteggio lo mostra. Il listato conta le chiamate di fib e la profondità massima della ricorsione, confronta il risultato con una versione iterativa (un riferimento indipendente, O(n) in tempo e O(1) in spazio) e con la forma chiusa 2·F(n+1) − 1, che è il numero esatto di chiamate.
# O(2^n) o no? Fibonacci ricorsivo: si contano le chiamate e la profondita' massima
import math
calls = 0
depth = 0
max_depth = 0
def fib(n):
global calls, depth, max_depth
calls += 1
depth += 1
max_depth = max(max_depth, depth)
result = n if n < 2 else fib(n - 1) + fib(n - 2)
depth -= 1
return result
def fib_iter(n): # riferimento indipendente, O(n) tempo e O(1) spazio
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
prev = None
print(f"{'n':>3} {'chiamate':>10} {'2F(n+1)-1':>10} {'rapporto':>9} {'prof. max':>9}")
for n in range(10, 31, 4):
calls = depth = max_depth = 0
assert fib(n) == fib_iter(n)
formula = 2 * fib_iter(n + 1) - 1 # forma chiusa del numero di chiamate
assert calls == formula
ratio = f"{calls / prev:.3f}" if prev else "-"
print(f"{n:>3} {calls:>10} {formula:>10} {ratio:>9} {max_depth:>9}")
prev = calls
phi = (1 + math.sqrt(5)) / 2
print("\nrapporto atteso fra n e n+4: phi^4 =", round(phi ** 4, 3), "(non 2^4 = 16)")
# Output:
# n chiamate 2F(n+1)-1 rapporto prof. max
# 10 177 177 - 10
# 14 1219 1219 6.887 14
# 18 8361 8361 6.859 18
# 22 57313 57313 6.855 22
# 26 392835 392835 6.854 26
# 30 2692537 2692537 6.854 30
#
# rapporto atteso fra n e n+4: phi^4 = 6.854 (non 2^4 = 16)Le chiamate corrispondono alla formula in ogni riga (l'assert non è scattato), e il rapporto fra n e n + 4 converge a 6,854 e non a 16: la crescita è Θ(φⁿ) con φ ≈ 1,618, il rapporto aureo, non 2ⁿ. La colonna della profondità dice altro: lo spazio usato dallo stack è lineare, n livelli, perché la ricorsione scende sempre prima sul ramo n − 1. Quindi lo stesso programma ha un tempo esponenziale e uno spazio lineare, e le due analisi vanno fatte separatamente.
Lo spazio extra, escluso l'ingresso, è la seconda risorsa da contare: una funzione «in loco» ne usa una quantità costante o logaritmica, una che copia l'ingresso ne usa una proporzionale. Nel prossimo articolo, Sorting algorithms: bubble, merge, quick, heap, vedrai che merge sort e quicksort hanno lo stesso tempo medio ma spazi molto diversi.
Analisi ammortizzata: l'append che a volte costa n
Alcune operazioni costano quasi sempre poco e ogni tanto moltissimo. L'append di una lista dinamica scrive in una cella libera, ma quando la memoria riservata è piena deve allocare un blocco più grande e copiare tutto. Il costo ammortizzato è il costo totale di una sequenza di operazioni diviso per il loro numero, e dipende dalla strategia di crescita. Il listato confronta due strategie su N append: raddoppiare la capacità e aumentarla di 16 posti ogni volta.
# Array dinamico: quante copie costa una sequenza di N append?
def appends(N, grow):
"""grow(cap) -> nuova capacita'. Restituisce copie totali e costo massimo di un singolo append."""
cap, size, copies, worst = 1, 0, 0, 0
for _ in range(N):
cost = 1 # la scrittura dell'elemento
if size == cap: # pieno: alloca e copia tutto
cost += size
copies += size
cap = grow(cap)
size += 1
worst = max(worst, cost)
return copies, worst
print(f"{'N':>8} | {'raddoppio: copie':>16} {'copie/N':>8} {'peggiore':>9} | {'+16: copie':>11} {'copie/N':>8}")
for N in (1000, 10000, 100000):
c2, w2 = appends(N, lambda c: 2 * c)
c16, _ = appends(N, lambda c: c + 16)
print(f"{N:>8} | {c2:>16} {c2 / N:>8.3f} {w2:>9} | {c16:>11} {c16 / N:>8.1f}")
# Metodo del conto bancario: ogni append incassa 'charge' unita' e spende il costo reale.
def min_bank(N, charge):
cap, size, bank, lowest = 1, 0, 0, 0
for _ in range(N):
cost = 1
if size == cap:
cost += size
cap *= 2
size += 1
bank += charge - cost
lowest = min(lowest, bank)
return lowest
print("\nsaldo minimo con addebito 2 per append:", min_bank(100000, 2))
print("saldo minimo con addebito 3 per append:", min_bank(100000, 3))
# Output:
# N | raddoppio: copie copie/N peggiore | +16: copie copie/N
# 1000 | 1023 1.023 513 | 31311 31.3
# 10000 | 16383 1.638 8193 | 3120625 312.1
# 100000 | 131071 1.311 65537 | 312456250 3124.6
#
# saldo minimo con addebito 2 per append: -65534
# saldo minimo con addebito 3 per append: 0Con il raddoppio le copie totali restano sotto 2N (1.023, 16.383 e 131.071 per N = 1.000, 10.000 e 100.000): sono sempre una potenza di due meno uno, quindi il rapporto copie/N oscilla fra 1 e 2 e non cresce. Con l'incremento fisso le copie per append salgono con N (31, 312, 3.124), perché la somma di una progressione aritmetica è quadratica. Il «peggiore» a destra resta enorme (65.537 per N = 100.000) e questo è il punto da ricordare: ammortizzato non vuol dire che ogni operazione sia veloce.
La seconda parte del listato è il metodo del conto bancario di Tarjan (Amortized Computational Complexity, SIAM Journal on Algebraic Discrete Methods, 1985, DOI 10.1137/0606031, di cui ho verificato i metadati ma non letto il testo). Ogni append incassa un'unità fissa e spende il costo reale; se il saldo non scende mai sotto zero, quell'addebito fisso è un limite superiore al costo ammortizzato. Con 3 unità il saldo minimo è 0 e il conto regge; con 2 unità il saldo arriva a −65.534 e l'argomento crolla. Il tre non è magico: una unità paga la scrittura, due si accumulano per ricopiare l'elemento stesso e un suo compagno al prossimo raddoppio.
E la lista vera? La documentazione di Python indica l'append come O(1) ammortizzato, con la nota che una singola operazione può costare O(n) quando lo spazio viene ridimensionato. Il secondo listato lo osserva dall'esterno, leggendo sys.getsizeof dopo ogni append.
# Come cresce davvero una list di CPython: si contano i cambi della capacita' riservata
import sys
lst = []
last, reallocs = sys.getsizeof(lst), 0
for i in range(1_000_000):
lst.append(i)
now = sys.getsizeof(lst)
if now != last:
reallocs += 1
last = now
print("Python", sys.version.split()[0])
print("append eseguiti: 1000000, cambi di capacita' osservati:", reallocs)
print("byte riservati alla fine:", sys.getsizeof(lst), "per", len(lst), "elementi")
print("rapporto riservato/usato:", round(sys.getsizeof(lst) / (8 * len(lst)), 3))
# Output:
# Python 3.14.4
# append eseguiti: 1000000, cambi di capacita' osservati: 86
# byte riservati alla fine: 8448728 per 1000000 elementi
# rapporto riservato/usato: 1.056Il risultato dipende dalla versione, e per questo è stampata: con Python 3.14.4 la capacità riservata è cambiata 86 volte in un milione di append, e alla fine la lista riserva circa il 5,6% di memoria in più del necessario. Pochi cambi, a distanza crescente, sono la firma di una crescita proporzionale e non costante. Non ricavare da qui un fattore di crescita come regola generale: è un dettaglio di implementazione che può cambiare.
Costruire il caso peggiore invece di sperarlo
Dichiarare un caso peggiore senza mostrarlo è un'abitudine pericolosa: l'ordinamento per inserzione è O(n²), ma quanto vale la costante, e quando si arriva a quel limite? Il listato lo implementa contando confronti e spostamenti, lo verifica su 2.000 ingressi casuali con seme fisso contro sorted e contro un riferimento indipendente (il numero di inversioni, cioè le coppie fuori ordine, calcolato per forza bruta), e poi costruisce i tre casi.
# Caso migliore, peggiore e medio costruiti, con il conteggio di confronti e spostamenti
import random
def insertion_sort(a):
a = a[:]
comparisons = moves = 0
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0:
comparisons += 1
if a[j] > key:
a[j + 1] = a[j]
moves += 1
j -= 1
else:
break
a[j + 1] = key
return a, comparisons, moves
def inversions(a): # riferimento indipendente: coppie fuori ordine, per forza bruta
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
rng = random.Random(2026) # seme fisso: stessa uscita a ogni esecuzione
for _ in range(2000): # correttezza e identita' moves == inversioni, su 2000 ingressi
a = [rng.randrange(50) for _ in range(rng.randrange(0, 30))]
out, _, moves = insertion_sort(a)
assert out == sorted(a) and moves == inversions(a)
print(f"{'n':>5} {'ordinato':>9} {'inverso':>9} {'n(n-1)/2':>9} {'casuale (media 200)':>20} {'n^2/4':>9}")
for n in (50, 100, 200, 400):
best = insertion_sort(list(range(n)))[1]
worst = insertion_sort(list(range(n, 0, -1)))[1]
avg = sum(insertion_sort(rng.sample(range(n), n))[1] for _ in range(200)) / 200
print(f"{n:>5} {best:>9} {worst:>9} {n * (n - 1) // 2:>9} {avg:>20.0f} {n * n / 4:>9.0f}")
# Output:
# n ordinato inverso n(n-1)/2 casuale (media 200) n^2/4
# 50 49 1225 1225 653 625
# 100 99 4950 4950 2569 2500
# 200 199 19900 19900 10080 10000
# 400 399 79800 79800 40331 40000Sull'ingresso già ordinato i confronti sono n − 1, e sull'ingresso inverso sono esattamente n(n − 1)/2: la tabella coincide con la formula in ogni riga. Il caso casuale, mediato su 200 esecuzioni a seme fisso, è prossimo a n²/4 e la differenza (653 contro 625 per n = 50) è il termine lineare che la formula esatta contiene e la sua forma semplificata ignora. Il fatto che gli spostamenti siano uguali alle inversioni, verificato 2.000 volte, spiega perché un ingresso quasi ordinato sia quasi gratis: il costo misura quanto l'ingresso è disordinato, non solo quanto è lungo.
Costanti nascoste e perché non basta la notazione
Big-O butta via le costanti, e in produzione le costanti decidono. Due algoritmi O(n log n) possono avere costi molto diversi per il modo in cui accedono alla memoria, e uno O(n²) può battere uno O(n log n) su ingressi piccoli. Non l'ho misurato qui, perché i conteggi di questo articolo sono volutamente indipendenti dalla macchina, e quindi non dicono nulla sui tempi: una cifra come «10 volte più veloce per la cache» senza una misura riproducibile è proprio il tipo di frase che questa serie evita.
Un riscontro documentato esiste però nella fonte: le note di implementazione dell'ordinamento di CPython (listsort.txt) dicono che una sequenza ordinata più corta di una lunghezza minima (minrun) viene allungata a quella lunghezza con un'inserzione binaria stabile, in cui la posizione si trova con una ricerca binaria, prima di essere fusa con le altre. Se l'inserzione, nel caso generale quadratica, finisce dentro l'ordinamento predefinito di Python, è perché la notazione asintotica descrive il comportamento per n grande e la pratica lavora spesso con n piccolo.
Come usare i conteggi nel tuo lavoro
Il metodo che questi listati ti mostrano si applica a qualunque funzione. Prima formuli un'ipotesi sulla complessità leggendo i cicli, poi instrumenti il codice con un contatore sulle operazioni che ti interessano (confronti, accessi, copie), poi lo esegui su dimensioni che raddoppiano e calcoli la pendenza log-log fra le coppie consecutive. Se la pendenza non coincide con l'ipotesi, hai trovato un errore nell'analisi o nel codice: è il momento più utile del processo, perché nessun cronometro te lo avrebbe detto con questa nettezza.
Il conteggio si affianca alla misura dei tempi, non la sostituisce. I tempi servono a capire se la costante è accettabile, e vanno riportati come intervalli, dichiarando macchina, versione e numero di esecuzioni. Il conteggio serve a capire come scalerà il tuo codice, e ha il vantaggio di essere identico su qualunque computer, ripetibile e confrontabile in una revisione di codice.
Quando la notazione asintotica non basta
- Ingressi piccoli: sotto qualche decina di elementi la costante domina e la classe asintotica può indicare l'algoritmo sbagliato.
- Operazioni non uniformi: contare «confronti» o «accessi» come unità uguali nasconde che una scrittura su disco costa ordini di grandezza più di una somma.
- Peggiore caso raro: un'operazione ammortizzata O(1) può comunque violare un obiettivo di latenza, se il suo picco cade nel momento sbagliato.
- Distribuzione degli ingressi: la media vale solo sotto l'ipotesi con cui è stata calcolata, e i dati reali raramente la rispettano.
Nessuno di questi limiti rende inutile la notazione; la rendono un primo filtro. Se due soluzioni hanno classi diverse e l'ingresso crescerà, la classe decide; se hanno la stessa classe o l'ingresso resterà piccolo, la decisione passa alla misura e alla leggibilità del codice.
Esercizi
- Nel primo listato usa f(n) = 5n² + 2n e trova a mano due testimoni c e n₀, poi verifica con un ciclo.
- Scrivi la ricerca binaria su una lista ordinata, contando i confronti, e verifica che non superino ⌊log₂ n⌋ + 1.
- Nel listato dell'array dinamico prova un fattore di crescita 1,5 invece di 2 e osserva il rapporto copie/N.
- Costruisci l'ingresso peggiore per la ricerca lineare con duplicati e spiega perché il peggiore resta n.
Gli esercizi sono in ordine di difficoltà, ma si possono fare in qualunque ordine: il secondo prepara l'articolo sulla ricerca, il terzo mostra che il «2» del raddoppio è una scelta e non una legge. Se non ti torna un risultato, riesegui il listato con un contatore in più invece di rileggere la teoria.
Domande frequenti
Che differenza c'è fra O(n) e Θ(n)?
O(n) è solo un limite superiore: una funzione che costa sempre 5 passi è anche O(n). Θ(n) dice che la crescita è lineare sia verso l'alto sia verso il basso, quindi descrive il costo con precisione, a meno di costanti.
Perché non basta cronometrare il codice?
Il tempo dipende dalla macchina, dal carico e dalla versione dell'interprete, e riguarda solo le dimensioni che hai provato. Il conteggio delle operazioni è identico ovunque e mostra come cresce il costo anche oltre le dimensioni misurate.
L'append di una lista Python è davvero O(1)?
È O(1) ammortizzato secondo la documentazione di Python: una sequenza di N append costa O(N) in totale, ma una singola operazione può costare O(n) quando la memoria riservata viene ampliata.
Che cosa sai fare adesso
Sai enunciare Big-O con i suoi testimoni e smentirlo con un controesempio, distinguere il caso migliore, medio e peggiore e costruirli invece di sperarli, e leggere una pendenza log-log come una diagnosi. Sai che «O(2ⁿ)» e «O(1) ammortizzato» sono affermazioni precise che si possono contare, e hai un metodo, ipotesi, contatore, pendenza, per verificare le tue. Il passo successivo, l'articolo sugli ordinamenti, applica lo stesso metodo a quattro algoritmi concreti; la ricerca lineare, binaria e con tabelle hash e le strutture lineari chiudono questo primo blocco della serie.
Nella stessa serie trovi anche gli alberi binari di ricerca e AVL e il riepilogo sulla programmazione dinamica.
Fonti
- Python Documentation - Time complexity of built-in types: presa la complessità di
list.appendcome O(1) ammortizzato e la nota sul ridimensionamento; consultata il 2026-11-13. - CPython, Objects/listsort.txt: presa la descrizione dell'inserzione binaria usata per le sequenze corte; letto il testo, consultato il 2026-11-13.
- R. E. Tarjan, Amortized Computational Complexity, SIAM J. Algebraic Discrete Methods 6(2), 1985: citata per il metodo del conto bancario; verificati titolo, autore e rivista via Crossref il 2026-11-13, testo non letto.
- Misure: i comandi sono i sette listati dell'articolo, eseguiti con Python 3.14.4 (
python3 -I) il 2026-11-13.
Commenti
Caricamento commenti...
Accedi per commentare