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 > 22-1
- T(4) = 1+T(3)+T(2) = 1+3+1 = 5 > 22-1
- T(5) = 1+T(4)+T(3) = 1+5+3 = 9 > 23-1
- T(6) = 1+T(5)+T(4) = 1+9+5 = 15 > 23-1
- T(7) = 1+T(6)+T(5) = 1+15+9 = 25 > 24-1
- T(8) = 1+T(7)+T(6) = 1+25+15 = 41 > 24-1
- …
- T(n) ≥ 2n/2-1.
Il tempo di attesa è esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande T(n) ∈ O(2n).
L’algoritmo ricorsivo per il calcolo dell’n-simo numero di Fibonacci ha complessità esponenziale!
Algoritmo iterativo
Si tratta di un algoritmo con un’iterazione semplice, senza chiamate ricorsive, quindi
- T(n) = c1+c2n
- T(n) ∈ O(n).
L’algoritmo iterativo per il calcolo dell’n-simo 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
- T(n) ∈ O(1).
Se consideriamo che per n molto grande l’operazione di elevamento a potenza potrebbe dipendere dal numero di cifre e che il numero di cifre del risultato cresce proporzionalmente al log di n allora si ottiene T(n) ∈ O(log n).
Conclusioni
| Metodo | Pro | Contro |
| Ricorsivo | Formulazione elegante | Numero di chiamate esponenziale! |
| Iterativo | Formulazione semplice | n passi, con operazioni elementari |
| Con formula | Valore “scientifico”. Numero di operazioni costante. |
|
Quindi
- per il calcolo dell’n-esimo numero di Fibonacci esistono più algoritmi con complessità molto diverse
- al crescere di n utilizzeremo l’algoritmo più conveniente
- ricorsivo, per n molto piccolo
- iterativo, …
- con formula, per n molto grande