Notazione asintotica

Algoritmi · Analisi della complessità

Notazione asintotica

La notazione asintotica descrive come cresce il costo di un algoritmo quando la dimensione dell’input diventa grande. Ignora dettagli di macchina e costanti, ma non la struttura del problema.

Che cosa stiamo misurando

Si sceglie una misura della dimensione n e si conta un’operazione dominante: confronti, accessi, somme o allocazioni. Il tempo T(n) e lo spazio S(n) sono funzioni di n, non secondi o megabyte precisi.

Input

n può essere il numero di elementi, vertici, bit o cifre. Va dichiarato.

Tempo

Conta quante volte si esegue un’operazione significativa.

Spazio ausiliario

Memoria aggiuntiva oltre all’input; include anche lo stack ricorsivo.

Modello, non cronometro. Due algoritmi con lo stesso Θ possono avere prestazioni reali diverse; l’analisi asintotica dice come scala la differenza, non quale vinca su ogni input.

Le cinque notazioni

Simbolo	Significato	Definizione	Lettura
O(g(n))	Limite superiore asintotico	0 ≤ f(n) ≤ cg(n)	Non cresce più velocemente di g, a costanti vicino.
Ω(g(n))	Limite inferiore asintotico	0 ≤ cg(n) ≤ f(n)	Cresce almeno quanto g.
Θ(g(n))	Limite stretto	c₁g(n) ≤ f(n) ≤ c₂g(n)	Stesso ordine di crescita.
o(g(n))	Limite superiore stretto	lim f(n)/g(n) = 0	f cresce strettamente più lentamente.
ω(g(n))	Limite inferiore stretto	lim f(n)/g(n) = ∞	f cresce strettamente più velocemente.

Nelle prime tre definizioni esistono costanti positive e una soglia n₀ oltre la quale la disuguaglianza vale. Θ(g(n)) equivale all’intersezione O(g(n)) ∩ Ω(g(n)).

O non significa “caso peggiore”. O è un limite superiore. Si può scrivere il tempo del caso migliore in O(n²), anche se è un’informazione poco precisa.

Ordini di crescita

Θ(1)Θ(log n)Θ(n)Θ(n log n)Θ(n²)Θ(n³)Θ(2ⁿ)Θ(n!)

Ordine	Nome	Esempio tipico	n = 1.000
Θ(1)	costante	accesso a un indice	1
Θ(log n)	logaritmico	ricerca binaria	≈ 10
Θ(n)	lineare	scansione	1.000
Θ(n log n)	linearitmico	merge sort	≈ 10.000
Θ(n²)	quadratico	doppi cicli	1.000.000
Θ(2ⁿ)	esponenziale	enumerazione di sottoinsiemi	impraticabile

Per log n è usata base 2. La base del logaritmo cambia solo per un fattore costante e quindi non cambia la classe Θ.

Regole pratiche di semplificazione

Elimina le costanti moltiplicative: 7n² = Θ(n²).
Conserva il termine dominante: 3n² + 10n + 50 = Θ(n²).
Blocchi in sequenza: somma e domina. Θ(n) + Θ(n log n) = Θ(n log n).
Cicli annidati indipendenti: moltiplica. n · n = Θ(n²).
Rami: specifica il caso. Il ramo più costoso descrive il caso peggiore, non necessariamente ogni esecuzione.
Ricorsione: scrivi una ricorrenza. Per esempio merge sort ha T(n)=2T(n/2)+Θ(n).

Caso migliore, medio, peggiore e ammortizzato

Migliore

Costo minimo tra gli input di dimensione n. È utile per descrivere algoritmi adattivi.

Medio

Valore atteso rispetto a un modello probabilistico degli input, che va dichiarato.

Peggiore

Costo massimo per input di dimensione n; offre una garanzia.

Ammortizzato

Costo medio per operazione su una sequenza, senza assumere input casuali.

Tre analisi rapide

Un solo ciclo

for i = 0 … n - 1
    visita A[i]

n iterazioni a costo costante: Θ(n).

Triangolo di confronti

for i = 0 … n - 1
    for j = i + 1 … n - 1

n(n−1)/2 = Θ(n²).

Dimezzamenti

while n > 1
    n = n / 2

Dopo k passi n/2ᵏ ≤ 1, quindi k = Θ(log n).

Errori comuni

Dire “questo algoritmo è O(n)” quando si conosce un limite stretto Θ(n): non è falso, ma è meno informativo.
Sommare complessità di cicli annidati invece di moltiplicarle, o moltiplicare cicli consecutivi invece di sommarli.
Ignorare il dominio dei parametri: counting sort dipende da n e dall’ampiezza k dei valori.
Confondere spazio totale e spazio ausiliario, o dimenticare lo stack delle chiamate ricorsive.

Prova tu

1 · Semplifica

8n³ + 2n² log n + 900

Soluzione

Θ(n³): il termine cubico domina n² log n.

2 · Conta

for (i = 1; i < n; i *= 3)

Soluzione

Θ(log₃ n) = Θ(log n).

3 · Confronta

È vero che n log n = o(n²)?

Soluzione

Sì: (n log n)/n² = (log n)/n tende a 0.