Equazioni di ricorrenza

Quando si calcola la complessità di un algoritmo ricorsivo, questa viene espressa tramite un’equazione di ricorrenza, ovvero una formula matematica definita in maniera... ricorsiva!

Un esempio è il Merge Sort:

$T (n) = {\begin{cases} c & n = 1 \\ 2 T (⌊ \frac{n}{2} ⌋) + d n & n > 1 \end{cases}$

da cui si ottiene

$T (n) = Θ (n \log n)$

Analizziamo quindi i diversi metodi per risolvere ricorrenze, ossia:

Analisi per livelli

“Srotoliamo” la ricorrenza in un albero i cui nodi rappresentano i costi ai vari livelli della ricorsione.

Esempio 1)

$T (n) = {\begin{cases} 1 & n \leq 1 \\ 4 T (\frac{n}{2}) + n & n > 1 \end{cases}$

Analizziamo cosa succede ad ogni livello:

Livello	Dimensione	Costo chiamata	N. chiamate	Costo livello (costo chiamate x n. chiamate)
$0$	$n$	$n$	$1$	$n$
$1$	$\frac{n}{2}$	$\frac{n}{2}$	$4$	$4 \frac{n}{2} = 2 n$
$2$	$\frac{n}{4}$	$\frac{n}{4}$	$16$	$16 \frac{n}{4} = 4 n$
$i$	$\frac{n}{2^{i}}$	$\frac{n}{2^{i}}$	$4^{i}$	$2^{i} n$
$\log n - 1$	$\frac{n}{2^{\log n - 1}}$	$\frac{n}{2^{\log n - 1}}$	$4^{\log n - 1}$	$2^{\log n - 1} \cdot n$
$\log n$	$1$	$T (1)$	$4^{\log n}$	$4^{\log n}$

Come si risolve?

\begin{aligned} T (n) & = \sum_{i = 0}^{penultimo livello} costo livello[i] + costo ultimo livello \\ = \overset{serie geometrica}{\overset{⏞}{\sum_{0}^{\log n - 1} 2^{i}}} \cdot n + 4^{\log n} = n \cdot \frac{2^{\log n} - 1}{2 - 1} + 4^{\log n} \\ = n (n - 1) + 2^{\log n^{2}} = n^{2} - n + n^{2} = 2 n^{2} - n \\ = Θ (n^{2}) \end{aligned}

Esempio 2)

$T (n) = {\begin{cases} 1 & n \leq 1 \\ 4 T (\frac{n}{2}) + n^{3} & n > 1 \end{cases}$

Analizziamo cosa succede ad ogni livello:

Livello	Dimensione	Costo chiamata	N. chiamate	Costo livello (costo chiamate x n. chiamate)
$0$	$n$	$n^{3}$	$1$	$n^{3}$
$1$	$\frac{n}{2}$	${(\frac{n}{2})}^{3}$	$4$	$4 {(\frac{n}{2})}^{3}$
$2$	$\frac{n}{4}$	${(\frac{n}{4})}^{3}$	$16$	$16 {(\frac{n}{4})}^{3}$
$i$	$\frac{n}{2^{i}}$	${(\frac{n}{2^{i}})}^{3}$	$4^{i}$	$4^{i} \cdot {(\frac{n}{2^{i}})}^{3}$
$\log n - 1$	$\frac{n}{2^{\log n - 1}}$	${(\frac{n}{2^{\log n - 1}})}^{3}$	$4^{\log n - 1}$	$4^{\log n - 1} {(\frac{n}{2^{\log n - 1}})}^{3}$
$\log n$	$1$	$T (1)$	$4^{\log n}$	$4^{\log n}$

Come si risolve?

\begin{aligned} T (n) & = \sum_{i = 0}^{penultimo livello} costo livello[i] + costo ultimo livello \\ = \sum_{i = 0}^{\log n - 1} 4^{i} \cdot {(\frac{n}{2^{i}})}^{3} + 4^{\log n} \\ = n^{3} \cdot \sum_{i = 0}^{\log n - 1} \frac{2^{2 i}}{2^{3 i}} + n^{2} \\ = n^{3} \cdot \sum_{i = 0}^{\log n - 1} {(\frac{1}{2})}^{i} + n^{2} \leq n^{3} \cdot \overset{serie geometrica}{\overset{⏞}{\sum_{i = 0}^{\infty} {(\frac{1}{2})}^{i}}} + n^{2} \\ \leq 2 n^{3} + n^{2} \end{aligned}

Possiamo quindi affermare che $T (n) = O (n^{3})$ , ossia la complessità di $T (n)$ è al massimo cubica. La dimostrazione precedente però non afferma che $T (n) = Θ (n^{3})$ , perché ad un certo punto siamo passati a $\leq$ .
Possiamo notare però che $T (n) \geq (n^{3})$ , visto che nell'equazione di ricorrenza c'è un $+ n^{3}$ . Quindi è possibile affermare che $T (n) = Ω (n^{3})$ e quindi $T (n) = Θ (n^{3})$ .

Analisi per tentativi (o per sostituzione)

È un metodo in cui si cerca di “indovinare” (guess) una soluzione, in base alla propria esperienza, e si dimostra che questa soluzione è corretta tramite induzione.

Esempio 1 - Intuizione corretta

$T (n) = {\begin{cases} 1 & n = 1 \\ T (⌊ \frac{n}{2} ⌋) + n & n > 1 \end{cases}$

Se siamo furbi possiamo notare che $T (n) = n + \frac{n}{2} + \frac{n}{4} + . . . \leq 2 n$ , tentiamo quindi di provare che $T (n) = O (n)$

CASO BASE: Dimostriamo la disequazione per $T (1)$
$T (1) = 1 \overset{?}{\leq} 1 \cdot c \Leftrightarrow \forall c \geq 1$ ✅

IPOTESI INDUTTIVA: $\forall k < n : T (k) \leq c k$
PASSO DI INDUZIONE: Dimostriamo la disequazione per $T (n)$ :

\begin{aligned} T (n) & = T (⌊ \frac{n}{2} ⌋) + n \\ \leq c ⌊ \frac{n}{2} ⌋ + n \\ \leq c \frac{n}{2} + n \\ = n (\frac{c}{2} + 1) \\ \overset{?}{\leq} c n \Leftrightarrow (\frac{c}{2} + 1) \leq c \Leftrightarrow c \geq 2 \end{aligned}

Abbiamo provato che $T (n) \leq c n$

Nel caso base: $c \geq 1$
Nel passo induttivo: $c \geq 2$
Un valore $c$ che rispetta entrambe le disequazioni è $c = 2$

Abbiamo quindi provato che $T (n) = O (n)$

É possibile dimostrare facilmente che $T (n) = Ω (n)$ :

T (n) = (⌊ \frac{n}{2} ⌋) + n \geq n \overset{?}{\geq} d n

che è vera per ogni $d \leq 1$ .

Esempio 2 - Interpretazione errata

$T (n) = {\begin{cases} 1 & n \leq 1 \\ T (n - 1) + n \end{cases}$

Si può facilmente intuire che $T (n) = Θ (n^{2})$ visto che $T (n) = n + (n - 1) + (n - 2) + . . . + 1$
Quindi:

T (n) = \sum_{i = 1}^{n} i = \frac{n (n + 1)}{2} = Θ (n^{2})

Ma se sbagliassimo l'intuizione?
Tentiamo per esempio di dimostrare che $T (n) = O (n)$ :

\begin{aligned} T (n) & = T (n - 1) + n \\ \leq c (n - 1) + n \\ \leq (c + 1) n - c \\ \leq (c + 1) n \\ \overset{?}{\leq} c n \Rightarrow c + 1 \leq c \end{aligned}

Come possiamo vedere la disequazione risulta impossibile, dunque $T (n) \neq O (n)$ .

Esempio 3 - Caso base errato

$T (n) = {\begin{cases} 1 & n \leq 1 \\ 9 T (⌊ \frac{n}{3} ⌋) + n & n > 1 \end{cases}$

Tentiamo di dimostrare che $T (n) = O (n^{2})$

IPOTESI INDUTTIVA: $\exists c > 0 : T (k) \leq c k^{2}, \forall k < n$
PASSO DI INDUZIONE: Dimostriamo la disequazione per $T (n)$ :

\begin{aligned} T (n) & = 9 T (⌊ \frac{n}{3} ⌋) + n \\ \leq 9 c {(⌊ \frac{n}{3} ⌋)}^{2} + n \\ \leq 9 c (\frac{n^{2}}{9}) + n \\ = c n^{2} + n \\ ≰ c n^{2} \end{aligned}

Mannaggia, se non ci fosse quel $+ n$ ...
Cerchiamo allora di dimostrare un'ipotesi induttiva più stretta:

IPOTESI INDUTTIVA: $\exists c > 0 : T (k) \leq c (k^{2} - k), \forall k < n$
PASSO DI INDUZIONE: Dimostriamo la disequazione per $T (n)$ :

\begin{aligned} T (n) & = 9 T (⌊ \frac{n}{3} ⌋) + n \\ \leq 9 c ({(⌊ \frac{n}{3} ⌋)}^{2} - \frac{n}{3}) + n \\ \leq c n^{2} - 3 c n + n \\ \overset{?}{\leq} c n^{2} - c n \Leftrightarrow c \geq \frac{1}{2} \end{aligned}

Perfetto, non ci resta che dimostrare il passo base

CASO BASE: Dimostriamo la disequazione per $T (1)$
$T (1) = 1 \overset{?}{\leq} c (1^{2} - 1) = 0$ ❌

Per $T (1)$ non funziona, proviamo allora per i successivi:
$T (2) = 9 T (\frac{2}{3}) + 2 = 9 T (0) + 2 = 9 + 2 = 11 \overset{?}{\leq} c (2^{2} - 2) \Leftrightarrow c \geq \frac{11}{2}$
$T (3) = 9 T (\frac{3}{3}) + 3 = 9 T (1) + 3 = 9 + 3 = 12 \overset{?}{\leq} c (3^{2} - 3) \Leftrightarrow c \geq 2$
$T (4) = 9 T (\frac{4}{3}) + 4 = 9 T (1) + 4 = 9 + 4 = 13 \overset{?}{\leq} c (4^{2} - 4) \Leftrightarrow c \geq \frac{13}{12}$
$T (5) = 9 T (\frac{5}{3}) + 5 = 9 T (1) + 5 = 9 + 5 = 14 \overset{?}{\leq} c (5^{2} - 5) \Leftrightarrow c \geq \frac{14}{20}$
$T (6) = 9 T (\frac{6}{3}) + 6$

Non è necessario andare oltre, perchè $T (6)$ dipende da $T (2)$ che è già stato dimostrato.
Concludiamo che $T (n) = O (n^{2})$

Per riassumere

Si “indovina” una possibile soluzione e si formula un’ipotesi induttiva
Si sostituisce nella ricorrenza le espressioni $T (\cdot)$ , utilizzando l’ipotesi induttiva
Si dimostra che la soluzione è valida anche per il caso base

Attenzione

Ad ipotizzare soluzioni troppo “strette”
Ad alcuni casi particolari che richiedono alcune astuzie matematiche
Ai casi base: il logaritmo può complicare le cose

Metodo dell'esperto (o delle ricorrenze comuni)

Esiste un’ampia classe di ricorrenze che possono essere risolte facilmente facendo ricorso ad alcuni teoremi, ognuno dei quali si occupa di una classe particolare di equazioni di ricorrenza.

Teorema 1 - Master Theorem)

Siano $a$ e $b$ costanti intere tali che $a \geq 1$ e $b \geq 2$ , e $c$ , $β$ costanti reali tali che $c > 0$ e $β \geq 0$ . Sia $T (n)$ data dalla relazione di ricorrenza:

$T (n) = {\begin{cases} d & n \leq 1 \\ a T (\frac{n}{b}) + c n^{β} & n > 1 \end{cases}$

allora

$T (n) = {\begin{cases} Θ (n^{\log_{b} a}) & \log_{b} a > β \\ Θ (n^{\log_{b} a} \log n) & \log_{b} a = β \\ Θ (n^{β}) & \log_{b} a < β \end{cases}$

Teorema 2)

Siano $a_{1}, a_{2}, . . ., a_{h}$ costanti intere non negative, con $h$ costante positiva, $c$ e $β$ costanti reali tali che $c > 0$ e $β \geq 0$ , e sia $T (n)$ definita dalla relazione di ricorrenza:

$T (n) = {\begin{cases} \sum_{1 \leq i \leq h} a_{i} T (n - i) + c n^{β} & n > m \\ Θ (1) & n < m \leq h \end{cases}$

Posto $a = \sum_{1 \leq i \leq h} a_{i}$ , allora:

$T (n)$ è $Θ (n^{β + 1})$ , se $a = 1$
$T (n)$ è $Θ (a^{n} n^{β})$ , se $a \geq 2$

In parole povere, sommi tutti i coefficienti di $T (n)$ .

Esempi

Ricorrenza	a	$β$	Risultato
$T (n) = T (n - 10) + n^{2}$	1	2	$Θ (n^{3})$
$T (n) = T (n - 2) + T (n - 1) + 1$	2	0	$Θ (2^{n} \cdot n^{0})$
$T (n) = 3 T (n - 69) + 4 T (n) + n$	7	1	$Θ (7^{n} \cdot n)$