Ricorrenze

Attraverso i metodi delle ricorrenze è possibile risolvere la ricorsione nelle complessità degli algoritmi.

Metodo dell'iterazione

La procedura consiste nell'esplodere la ricorsione fino a trovare un pattern, come:

$$\begin{gathered} T(n)=\{\begin{array}{ll}c+T\left(\frac{n}{2}\right)& \text{se }n\ge 2\\ 1& \text{se }n=1\end{array} \\ \Downarrow \\ \begin{array}{rl}T(n)& =c+\left(c+T\left(\frac{n}{2}\right)\right)=\\ & =2c+T\left(\frac{n}{2^2}\right)=\\ & =2c+\left(c+T\left(\frac{n}{2^3}\right)\right)=\\ & =3c+T\left(\frac{n}{2^3}\right)=\\ & =kc+T\left(\frac{n}{2^k}\right)\end{array} \end{gathered}$$ che viene esploso fino ad arrivare al caso base, quando l'argomento è $1$, cioè: $$\frac{n}{2^k}=1\iff n=2^k\iff k={\log }_{2}n$$ quindi dopo essere stato esploso fino al caso base con $k={\log }_{2}n$, si ottiene: $$\begin{array}{rl}T(n)& =kc+T\left(\frac{n}{2^k}\right)=c{\log }_{2}n+T(1)=\\ & =c{\log }_{2}n+1=\Theta ({\log }_{2}n)\end{array}$$

Per esempio, se $$\begin{gathered} T(n)=\{\begin{array}{ll}9T\left(\frac{n}{3}\right)+n& \text{se }n\ge 2\\ 1& \text{se }n=1\end{array} \\ \Downarrow \\ \begin{array}{rl}T(n)& =9\left(9T\left(\frac{n}{3^2}\right)+\frac{n}{3}\right)+n=\\ & =9^{2}T\left(\frac{n}{3^2}\right)+3n+n=\\ & =9^{3}T\left(\frac{n}{3^3}\right)+3^{2}n+3n+n=\\ & =9^{3}T\left(\frac{n}{3^3}\right)+n(3^2+3+1)=\\ & =9^{k}T\left(\frac{n}{3^k}\right)+n\sum _{i=0}^{k-1}{3}^i=\\ & =9^{k}T\left(\frac{n}{3^k}\right)+n\cdot \frac{3^k-1}{3-1}\end{array} \end{gathered}$$ per la serie geometrica, fino al caso base in cui: $$\begin{gathered} \frac{n}{3^k}=1\iff k={\log }_{3}n \\ \Downarrow \\ T(n)=9^{{\log }_{3}n}\cdot T(1)+n\cdot \frac{3^{{\log }_{3}n}-1}{2}=n^2+\frac{n(n-1)}{2}=\Theta (n^2) \end{gathered}$$

Metodo della sostituzione

In questo caso si indovina la complessità e si dimostra per induzione, come per: $$T(n)=\{\begin{array}{ll}T\left(\lfloor \frac{n}{2}\rfloor \right)+n& \text{se }n\ge 2\\ 1& \text{se }n=1\end{array}$$ si dimostra che $T(n)=O(n)$, cioè che: $$\exists c>0,n_0\in \mathbb{N}:\forall n\ge n_0,T(n)\le c\cdot n$$ per il caso base ipotizzando sia $n_0=1$ allora $T(1)\le c\cdot 1\iff c\ge 1$, quindi: $$\begin{array}{rl}T(n)& =T\left(\lfloor \frac{n}{2}\rfloor \right)+n\\ & \le c\cdot \lfloor \frac{n}{2}\rfloor +n\\ & \le c\cdot \frac{n}{2}+n\\ & \le \left(\frac{c}{2}+1\right)\cdot n\end{array}$$ dove $T\left(\lfloor \frac{n}{2}\rfloor \right)\le c\cdot \lfloor \frac{n}{2}\rfloor$ perchè il caso base ha provato la proprietà fino a $n-1$ e $\lfloor \frac{n}{2}\rfloor \le n-1$, mentre $c\cdot \lfloor \frac{n}{2}\rfloor \le c\cdot \frac{n}{2}$ perchè l'intero prima è sempre più piccolo. Va quindi dimostrato che $\left(\frac{c}{2}+1\right)\cdot n\le c\cdot n$: $$\frac{c}{2}+1\le c\iff 2\le c$$ che è valido perchè $c\ge 2\ge 1$ dal caso base.

Teorema Master

Se consideriamo un algoritmo come la suddivisione in sottoproblemi, si ha: $$\begin{array}{rl}T(n)& =T_{\text{split}}(n)+\sum _{i=1}^{a}T\left(\frac{n}{b}\right)+T_{\text{merge}}(n)=\\ & =T\left(\frac{n}{b}\right)\cdot \sum _{i=1}^{a}1+f(n)=\\ & =a\cdot T\left(\frac{n}{b}\right)+f(n)\end{array}$$ dove $f(n)=T_{\text{split}}(n)+T_{\text{merge}}(n)$ è il tempo della suddivisione in $a$ sottoproblemi grandi $\frac{n}{b}$. Quindi: $$\begin{gathered} T(n)=\{\begin{array}{ll}a\cdot T\left(\frac{n}{b}\right)+f(n)& \text{se }n\ge 2\\ 1& \text{se }n=1\end{array} \\ \Updownarrow \\ a\ge 1\wedge b>1\wedge f(n)\ge 0 \end{gathered}$$

Allora dato un $d={\log }_{b}a$, si ha:

• Caso 1

  $$\begin{gathered} \exists ϵ>0:f(n)=O(n^{d-ϵ}) \\ \Downarrow \\ T(n)=\Theta (n^d) \end{gathered}$$ per cui la complessità è dominata dalla parte ricorsiva $a\cdot T\left(\frac{n}{b}\right)$.

  Per esempio, se $$T(n)=9T\left(\frac{n}{3}\right)+n$$ allora $a=9\ge 1$, $b=3>1$ e $f(n)=n\ge 0$ per cui: $$d={\log }_{3}9=2$$ e $f(n)=O(n^{2-ϵ})$ se per esempio $ϵ=1$ allora $n=O(n^{2-1})=O(n)$ quindi $T(n)=\Theta (n^2)$.

• Caso 2

  $$\begin{gathered} f(n)=\Theta (n^d) \\ \Downarrow \\ T(n)=\Theta (n^d\log n) \end{gathered}$$ allora la complessità della parte di suddivisione e ricorsiva si equivalgono.

  Per esempio, se $$T(n)=T\left(\frac{n}{2}\right)+c$$ allora $a=1\ge 1$, $b=2>1$ e $f(n)=c\ge 0$ per cui: $$d={\log }_{2}1=0$$ e $f(n)=\Theta (n^d)\iff c=\Theta (1)$ che corrisponde al caso 2, di conseguenza $T(n)=\Theta (\log n)$.

• Caso 3

  $$\begin{gathered} \exists ϵ>0:f(n)=\Omega (n^{d+ϵ})\wedge \exists 0<c<1:a\cdot f\left(\frac{n}{b}\right)\le c\cdot f(n) \\ \Downarrow \\ T(n)=\Theta (f(n)) \end{gathered}$$ per cui, se ci vuole più tempo per dividere il padre in $a$ figli che per dividere tutti gli $a$ figli (per la condizione ausiliaria), allora la complessità è dominata dalla parte di suddivisione $f(n)$.

  Per esempio, se $$T(n)=3T\left(\frac{n}{9}\right)+n$$ allora $a=3\ge 1$, $b=9>1$ e $f(n)=n\ge 0$ per cui: $$d={\log }_{9}3=\frac{1}{2}$$ e $f(n)=\Omega (n^{\frac{1}{2}+ϵ})$ se per esempio $ϵ=\frac{1}{2}$ allora $n=\Omega (n)$ e va trovata $0<c<1$ per cui:
  $$\begin{array}{rl}a\cdot f\left(\frac{n}{b}\right)\le c\cdot f(n)& \iff 3\cdot f\left(\frac{n}{9}\right)\le c\cdot f(n)\\ & \iff \frac{n}{3}\le c\cdot n\\ & \iff \frac{1}{3}\le c\end{array}$$ che è valido perchè $0<\frac{1}{3}\le c<1$ dalla condizione, quindi $T(n)=\Theta (f(n))=\Theta (n)$.

Dimostrazione

Esplodendo il tempo $T(n)=aT(\frac{n}{b})+f(n)$ si trova che, e.g. con $a=2$:

ovvero che al livello $i\le l$ ci sono $a^i$ nodi e i sottoproblemi sono grandi $\frac{n}{b^i}$, per cui: $$T(n)=f(n)+2f\left(\frac{n}{b}\right)+4f\left(\frac{n}{b^2}\right)+...=\sum _{i=0}^l{a}^{i}f\left(\frac{n}{b^i}\right)$$ dove $a^{i}f(\frac{n}{b^i})$ è il tempo per finire le chiamate al livello $i$, e all'ultimo livello $i=l$: $$\frac{n}{b^l}=1\iff n=b^l\iff l={\log }_{b}n$$ da cui si può ricavare il numero di foglie: $$a^{{\log }_{b}n}=a^{\frac{{\log }_{a}n}{{\log }_{a}b}}=a^{{\log }_{a}n\cdot {\log }_{b}a}=n^{{\log }_{b}a}=n^d$$ da cui deriva la $d={\log }_{b}a$ del teorema, e con cui si può trovare il numero di nodi: $$\sum _{i=0}^{{\log }_{b}n}{a}^i=\frac{a^{{\log }_{b}n+1}-1}{a-1}=\frac{a\cdot n^d-1}{a-1}=\Theta (n^d)$$

• Caso 1

  Per ipotesi $f(n)=O(n^{d-ϵ})$, quindi va dimostrato che $T(n)=\Theta (n^d)$: $$a^{i}f\left(\frac{n}{b^i}\right)=a^{i}O\left({\left(\frac{n}{b^i}\right)}^{d-ϵ}\right)=O\left(a^i\frac{n^{d-ϵ}}{(b^i{)}^{d-ϵ}}\right)=O\left(\cancel{a^i}\frac{n^{d-ϵ}}{\underset{d={\log }_{b}a}{\underbrace{\cancel{(b^d{)}^i}}}(b^i{)}^{-ϵ}}\right)=O(n^{d-ϵ}(b^{ϵ}{)}^i)$$ con cui si può trovare che: $$\begin{array}{rl}T(n)& =\sum _{i=0}^{{\log }_{b}n}{a}^{i}f\left(\frac{n}{b^i}\right)=\sum _{i=0}^{{\log }_{b}n}O((b^{ϵ}{)}^i{n}^{d-ϵ})=O\left(n^{d-ϵ}\sum _{i=0}^{{\log }_{b}n}(b^{ϵ}{)}^i\right)=\\ & =O\left(n^{d-ϵ}\frac{(b^{ϵ}{)}^{{\log }_{b}n+1}-1}{b^{ϵ}-1}\right)=O(n^{d-ϵ}\cdot \underset{O(n^{ϵ})}{\underbrace{\frac{n^{ϵ}\cdot b^{ϵ}-1}{b^{ϵ}-1}}})=O(n^{d-ϵ}\cdot n^{ϵ})=O(n^d)\end{array}$$ e anche $T(n)=\Omega (n^d)$ è verificato perchè $n^d$ è il numero di foglie che verranno sicuramente visitate.

• Caso 2

  Per ipotesi $f(n)=\Theta (n^d)$, quindi va dimostrato che $T(n)=\Theta (n^d\log n)$: $$a^{i}f\left(\frac{n}{b^i}\right)=a^i\Theta \left({\left(\frac{n}{b^i}\right)}^d\right)=\Theta \left(\cancel{a^i}\frac{n^d}{\cancel{(b^d{)}^i}}\right)=\Theta (n^d)$$ da cui si trova che: $$T(n)=\sum _{i=0}^{{\log }_{b}n}{a}^{i}f\left(\frac{n}{b^i}\right)=\sum _{i=0}^{{\log }_{b}n}\Theta (n^d)=\Theta \left(n^d\sum _{i=0}^{{\log }_{b}n}1\right)=\Theta (n^d({\log }_{b}n+1))=\Theta (n^d\log n)$$

• Caso 3

  Per ipotesi $f(n)=\Omega (n^{d+ϵ})$ e $\exists 0<c<1:af\left(\frac{n}{b}\right)\le c\cdot f(n)$ cioè, che per ogni livello $i$: $$a^{i}f\left(\frac{n}{b^i}\right)\le c^{i}f(n)$$ e va quindi dimostrato che $T(n)=\Theta (f(n))$, per cui: $$T(n)=\sum _{i=0}^{{\log }_{b}n}{a}^{i}f\left(\frac{n}{b^i}\right)\le \left(\sum _{i=0}^{{\log }_{b}n}{c}^{i}f(n)=f(n)\sum _{i=0}^{{\log }_{b}n}{c}^i\right)\le \left(f(n)\sum _{i=0}^{\infty }{c}^i=f(n)\frac{1}{1-c}\right)$$ e quindi $T(n)=O(f(n))$ dato che $\frac{1}{1-c}\in (1,\infty )$. Inoltre $T(n)=\Omega (f(n))$ perchè si sa che: $$T(n)=\underset{\ge 0}{\underbrace{aT\left(\frac{n}{b}\right)}}+f(n)\ge f(n)$$