Complessità: i numeri di Fibonacci

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo.

Algoritmo ricorsivo

Il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive

T(1) = 1
T(2) = 1
T(3) = 1 + T(2)+T(1) = 1 + 1 + 1 = 3 ( $2\cdot 2 -1$ )
T(4) = 1 + T(3)+T(2) = 1 + 3 + 1 = 5 ( $2\cdot 3 -1$ )
T(5) = 1 + T(4)+T(3) = 1 + 5 + 3 = 9 ( $2\cdot 5 -1$ )
T(6) = 1 + T(5)+T(4) = 1 + 9 + 5 = 15 ( $2\cdot 8 -1$ )
T(7) = 1 + T(6)+T(5) = 1 + 15 + 9 = 25 ( $2\cdot 13 -1$ )
T(8) = 1 + T(7)+T(6) = 1 + 25 + 15 = 41 ( $2\cdot 21 -1$ )
…
T(n) = $2\cdot F(n)-1$

La successione del numero di chiamate cresce come i numeri stessi di Fibonacci.
Si può dimostrare che i numeri di Fibonacci crescono in modo esponenziale.

Quindi $T(n)$ = $2\cdot F(n)-1$ ~ F(n) ~ $\gamma^n$

L’algoritmo ricorsivo per il calcolo dell’n-esimo numero di Fibonacci ha complessità in tempo esponenziale!

Algoritmo iterativo

Si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi

T(n) = $c_1\cdot n + c_2$ .

L’algoritmo iterativo per il calcolo dell’n-esimo numero di Fibonacci ha complessità lineare!

Con formula

Se consideriamo costante il tempo necessario per svolgere le singole operazioni presenti nella formula allora T(n) = c.
Per n molto grande il tempo per l’elevamento a potenza dipende dal logaritmo di n.

Conclusioni

Metodo	Pro	Contro	Quando?
Ricorsivo	Formulazione elegante	Numero di chiamate esponenziale!	Per n piccolo
Iterativo	Formulazione semplice Numero di operazioni lineare Operazioni elementari		Sempre…
Con formula	Ha un valore storico Numero di operazioni costante (logaritmico…)	Difficile da ricordare Numeri irrazionali	Per n molto grande