Equazioni di ricorrenza e Master Theorem

Algoritmi · Analisi della complessità

Equazioni di ricorrenza e Master Theorem

Le ricorrenze traducono la struttura di un algoritmo ricorsivo in un’equazione. Il Master Theorem permette di risolvere rapidamente molti algoritmi divide et impera, purché se ne verifichino davvero le ipotesi.

Perché compaiono le ricorrenze

Un algoritmo ricorsivo risolve un’istanza usando una o più istanze più piccole. Il suo tempo di esecuzione dipende quindi dal costo delle chiamate ricorsive e dal lavoro svolto fuori da esse.

T (n) = costo delle chiamate ricorsive + lavoro locale

Ricerca binaria

$T (n) = T (n / 2) + Θ (1)$ : una sola metà e lavoro costante.

Merge sort

$T (n) = 2 T (n / 2) + Θ (n)$ : due metà e fusione lineare.

Ricorsione lineare

$T (n) = T (n - 1) + Θ (n)$ : il problema diminuisce di una unità.

Serve sempre un caso base. Per esempio

T (1) = Θ (1)

. Senza una condizione di arresto, la ricorrenza non descrive un algoritmo terminante.

Come leggere una ricorrenza divide et impera

T (n) = a T (n / b) + f (n)

$a$ — sottoproblemi

Numero di chiamate ricorsive generate da ogni istanza. Deve essere almeno 1.

$b$ — riduzione

Ogni sottoproblema ha dimensione $n / b$ . Nel teorema si richiede $b > 1$ .

$f (n)$ — lavoro locale

Divisione del problema, combinazione dei risultati e ogni operazione non ricorsiva.

Il costo delle sole foglie dell’albero di ricorsione è determinato da

a^{\log_{b} n} = n^{\log_{b} a}

Per questo il termine critico del Master Theorem è $n^{\log_{b} a}$ : confronta la crescita delle foglie con quella del lavoro $f (n)$ .

Metodi di risoluzione

Espansione iterativa

Sostituisci ripetutamente la ricorrenza finché raggiungi il caso base, poi riconosci e sommi la serie ottenuta.

Albero di ricorsione

Calcola il costo di ogni livello, il numero di livelli e il costo delle foglie. È intuitivo e aiuta a formulare un’ipotesi.

Sostituzione

Ipotizza un limite asintotico e dimostralo per induzione, scegliendo con attenzione costanti e caso base.

Master Theorem

Classifica in pochi passaggi le ricorrenze bilanciate della forma $a T (n / b) + f (n)$ .

Mini-esempio per espansione

Per $T (n) = T (n - 1) + n$ :

\begin{matrix} T (n) & = & T (n - 2) + (n - 1) + n \\ = & T (1) + \sum_{i = 2}^{n} i \\ = & Θ (n^{2}) \end{matrix}

Questa ricorrenza non è nella forma del Master Theorem, perché la dimensione passa da $n$ a $n - 1$ , non a $n / b$ .

Master Theorem

Sia

T (n) = a T (n / b) + f (n)

Confronta $f (n)$ con $n^{c}$ . Non basta vedere quale sembra più grande: nei casi 1 e 3 la differenza deve essere polinomiale.

Caso	Confronto	Risultato	Intuizione
1	$f (n) = O (n^{c - ε})$ , per un $ε > 0$	$T (n) = Θ (n^{c})$	Dominano le foglie.
2	$f (n) = Θ (n^{c} \log^{k} n)$ , con $k \geq 0$	$T (n) = Θ (n^{c} \log^{k + 1} n)$	Tutti i livelli contribuiscono.
3	$f (n) = Ω (n^{c + ε})$ , per un $ε > 0$	$T (n) = Θ (f (n))$	Domina il lavoro vicino alla radice.

Nel caso 3 serve anche la condizione di regolarità: deve esistere una costante

q < 1

tale che

a f (n / b) \leq q f (n)

per ogni

n

sufficientemente grande. Impedisce oscillazioni patologiche del lavoro locale.

Procedura pratica

Riscrivi la ricorrenza nella forma $a T (n / b) + f (n)$ .
Identifica $a$ , $b$ e $f (n)$ . Non confondere $b$ con la dimensione $n / b$ .
Calcola $c = \log_{b} a$ e quindi $n^{c}$ .
Confronta asintoticamente $f (n)$ e $n^{c}$ , verificando l’eventuale fattore polinomiale.
Se sei nel caso 3, controlla esplicitamente la regolarità.
Scrivi il risultato in notazione $Θ$ , non soltanto $O$ , perché il teorema fornisce un limite asintotico stretto.

Esempi svolti

Ricorrenza	$n^{\log_{b} a}$	Caso	Soluzione
$T (n) = T (n / 2) + 1$	$n^{0} = 1$	2, con $k = 0$	$Θ (\log n)$
$T (n) = 2 T (n / 2) + n$	$n$	2, con $k = 0$	$Θ (n \log n)$
$T (n) = 8 T (n / 2) + n^{2}$	$n^{3}$	1	$Θ (n^{3})$
$T (n) = 7 T (n / 2) + n^{2}$	$n^{\log_{2} 7}$	1	$Θ (n^{\log_{2} 7}) \approx Θ (n^{2.807})$
$T (n) = 3 T (n / 4) + n \log n$	$n^{\log_{4} 3}$	3, con regolarità	$Θ (n \log n)$

Nell’ultimo esempio $\log_{4} 3 \approx 0.792$ , quindi $n \log n$ è polinomialmente più grande. Inoltre il rapporto $3 f (n / 4) / f (n)$ tende a $3 / 4$ , dunque la regolarità è soddisfatta per un opportuno $q < 1$ .

Quando il Master Theorem non si applica

Sottoproblemi di dimensioni diverse: $T (n) = T (n / 3) + T (2 n / 3) + n$ .
Riduzione sottrattiva: $T (n) = T (n - 1) + n$ .
Numero di sottoproblemi non costante: per esempio $n T (n / 2)$ .
Divario non polinomiale: funzioni come $n^{c} \log \log n$ non rientrano nella versione standard dei tre casi.
Regolarità non verificata: il solo fatto che $f (n)$ sia più grande non basta per usare il caso 3.

In questi casi usa espansione, albero di ricorsione o sostituzione. Per ricorrenze divide et impera più generali può essere utile il teorema di Akra–Bazzi.

I pavimenti e soffitti, come $T (⌊ n / b ⌋)$ , vengono spesso omessi durante l’analisi asintotica quando non cambiano l’ordine di crescita; in una dimostrazione rigorosa vanno comunque gestiti.

Errori comuni

Applicare il teorema prima di controllare che la ricorrenza abbia davvero la forma richiesta.
Confrontare $f (n)$ con $\log_{b} a$ invece che con $n^{\log_{b} a}$ .
Dire “caso 1” o “caso 3” per una differenza soltanto logaritmica: quei casi richiedono un divario polinomiale.
Dimenticare il fattore logaritmico aggiuntivo nel caso 2.
Ignorare il costo di divisione e combinazione quando si costruisce $f (n)$ .
Usare $O$ quando il risultato ottenuto è il più informativo $Θ$ .

Esercizi con soluzione

1. Ricorrenza di base

Risolvi $T (n) = 4 T (n / 2) + n$ .

Mostra soluzione

$a = 4$ , $b = 2$ e $n^{\log_{2} 4} = n^{2}$ . Poiché $f (n) = n$ , è il caso 1: $T (n) = Θ (n^{2})$ .

2. Fattore logaritmico

Risolvi $T (n) = 2 T (n / 2) + n \log n$ .

Mostra soluzione

$n^{\log_{2} 2}$ è $n$ e $f (n) = Θ (n \log^{1} n)$ . Caso 2 con $k = 1$ : $Θ (n \log^{2} n)$ .

3. Domina la radice

Risolvi $T (n) = 2 T (n / 2) + n^{2}$ .

Mostra soluzione

Il termine critico è $n$ , mentre $n^{2}$ è polinomialmente più grande. La regolarità vale perché $2 {(n / 2)}^{2} = n^{2} / 2$ . Caso 3: $Θ (n^{2})$ .

4. Riconosci il limite

Si può applicare il Master Theorem a $T (n) = T (n - 2) + 1$ ?

Mostra soluzione

No. La riduzione è sottrattiva, non divisiva. Espandendo si eseguono circa $n / 2$ passi a costo costante, quindi $T (n) = Θ (n)$ .

5. Quicksort sbilanciato

Nel caso peggiore, quicksort può generare $T (n) = T (n - 1) + Θ (n)$ . Trova l’ordine di crescita.

Mostra soluzione

L’espansione produce $n + (n - 1) + \dots + 1$ . La somma è $Θ (n^{2})$ .

6. Caso di confine

La versione standard qui presentata classifica $T (n) = 2 T (n / 2) + n \log \log n$ ?

Mostra soluzione

No. Il termine $n \log \log n$ è più grande di $n$ , ma non di un fattore polinomiale, e non ha la forma $Θ (n \log^{k} n)$ con $k \geq 0$ costante.

Promemoria: identifica la forma, calcola $n^{\log_{b} a}$ , confronta con $f (n)$ e verifica tutte le ipotesi prima di scegliere il caso.

Perché compaiono le ricorrenze

Ricerca binaria

Merge sort

Ricorsione lineare

Come leggere una ricorrenza divide et impera

a — sottoproblemi

b — riduzione

f(n) — lavoro locale

Metodi di risoluzione

Espansione iterativa

Albero di ricorsione

Sostituzione

Master Theorem

Mini-esempio per espansione

Master Theorem

Procedura pratica

Esempi svolti

Quando il Master Theorem non si applica

Errori comuni

Esercizi con soluzione

1. Ricorrenza di base

2. Fattore logaritmico

3. Domina la radice

4. Riconosci il limite

5. Quicksort sbilanciato

6. Caso di confine

$a$ — sottoproblemi

$b$ — riduzione

$f (n)$ — lavoro locale