Fibonacci

Calcoliamo la sequenza di Fibonacci f(n)=\begin{equation}\begin{cases}1 & \mbox{se } n=0\\ 1 & \mbox{se } n=1 \\ f(n-1)+f(n-2) & \mbox{altrimenti}\end{cases}\end{equation}

fib(n):
	if n == 0 or n == 1 then
		return 1
	else
		return fib(n-1) + fib(n-2)

Calcoliamo $T(n)$: T(n)=\begin{equation}\begin{cases}2 & \mbox{se } n=2 \\ T(n-1)+T(n-2) & \mbox{altrimenti}\end{cases}\end{equation}

Quando $n=2$ si devono fare due chiamate: fib(0) e fib(1).

Dal momento che $T(n-2)\le T(n-1)$ e che $T(n)\le 2\cdot T(n-1)$ si ha che \begin{align}T(n) = T(n-1)+T(n-2) & \le 2 \cdot T(n-1) \\ & \le 2 \cdot 2 \cdot T(n-2) \\ & \le ... \\ & \le 2^i\cdot T(n-i) \\ & \le 2^{n-2} \cdot T(n-(n-2)) = 2^{n-2}\cdot T(2) = 2^{n-1}\end{align} $\Rightarrow T(n)\in O(2^n)$

Similmente si può dire che

T(n) = T(n-1)+T(n-2) & \ge 2 \cdot T(n-2) \\ & \ge 2 \cdot 2 \cdot T(n-4) \\ & \ge 2 \cdot 2 \cdot 2 \cdot T(n-6) \\ & \ge ... \\ & \ge 2^i\cdot T(n-2i) \\ & \ge 2^{\frac{n}2-1} \cdot T(n-2(\frac{n}2-1)) = 2^{\frac{n}2-1} \cdot T(2) = 2^{\frac{n}2}\end{align}$$ Mi posso fermare quando moltiplico per T(2), quindi si deve avere `n-2i=2`, ovvero quando $i = \frac{n}2-1$ $\Rightarrow T(n) \in \Omega(2^{\frac{n}{2}})$ L'algoritmo quindi ha un costo esponenziale, anche perché la dimensione dell'input è logn, che sono i bit che servono per rappresentare il numero n. $\Rightarrow \Theta(2^n)$ ## Soluzione iterativa Sopra si è discusso di una soluzione [[ricorsione|ricorsiva]], con un costo computazionale molto elevato. Esiste un algoritmo molto meno costoso. Se si utilizza l'iterazione, il costo cala drasticamente. ``` fib(n): if n == 0 then return 0 if n == 1 then return 1 min1 := 0 min2 := 1 for i=2 to n: temp := min1 + min2 min1 := min2 min2 := temp return min1 + min2 ``` #asd_10