Complessità: 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 > 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 è maggiore di un tempo 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 a n allora si ottiene di nuovo una complessità lineare.

Conclusioni

Dato un certo problema, il calcolo dell’n-esimo numero di Fibonacci, possiamo individuare diversi algoritmi con complessità diverse.

Per n abbastanza grande utilizzeremo quello con la complessità più bassa!

Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità: numeri di Fibonacci

Comments are closed.