Complessità di "Fibonacci"

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Complessità di "Fibonacci"

Il problema di calcolare l'n-esimo numero di Fibonacci ammette una soluzione ricorsiva e una soluzione iterativa con complessità molto diverse...

Soluzione ricorsiva

function FiboRic(N: LongInt): LongInt;
begin
   if(N <= 2) then
      FiboRic:=1
   else
      FiboRic:=FiboRic(N-1)+FiboRic(N-2);
end;

Se consideriamo che il tempo di attesa è proporzionale al numero di chiamate ricorsive allora calcoliamo quest'ultimo valore

T(1) = 1
T(2) = 1
T(3) = 1+T(2)+T(1) = 1+1+1 = 3
T(4) = 1+T(3)+T(2) = 1+3+1 = 5
T(5) = 1+T(4)+T(3) = 1+5+3 = 9
T(6) = 1+T(5)+T(4) = 1+9+5 = 15
T(7) = 1+T(6)+T(5) = 1+15+9 = 25
T(8) = 1+T(7)+T(6) = 1+25+15 = 41
T(9) = 1+T(8)+T(7) = 1+41+25 = 67
...

Sembra una sequenza strana ma se accettiamo una certa approssimazione

T(1) = 1
T(2) = 1
T(3) = 1+T(2)+T(1) ≥ 2*T(1)+1 = 3 = 2²-1
T(4) = 1+T(3)+T(2) ≥ 2*T(2)+1 = 3
T(5) = 1+T(4)+T(3) ≥ 2*T(3)+1 ≥ 7 = 2³-1
T(6) = 1+T(5)+T(4) ≥ 2*T(4)+1 ≥ 7
T(7) = 1+T(6)+T(5) ≥ 2*T(5)+1 ≥ 15 = 2⁴-1
T(8) = 1+T(7)+T(6) ≥ 2*T(6)+1 ≥ 15
T(9) = 1+T(8)+T(7) ≥ 2*T(7)+1 ≥ 31 = 2⁵-1
...

Quindi

T(n) ≥ 2^n/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(2ⁿ)

Il tempo di attesa per calcolare l'n-esimo numero di Fibonacci, utilizzando l'algoritmo ricorsivo, è esponenziale!

Soluzione iterativa

function FiboIter(N: LongInt): LongInt;
Var
   I, A, B, C: LongInt;
begin
   if(N <= 2) then
      FiboIter:=1
   else
      begin
         A:=1;
         B:=1;
         for I:=3 to N do
            begin
               C:=A+B;
               A:=B;
               B:=C;
            end;
         FiboIter:=C;
      end;
end;

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

T(n) = c₁+c₂n ε O(n)

Allora il tempo di attesa per calcolare l'n-esimo numero di Fibonacci, utilizzando l'algoritmo iterativo, è lineare!

Soluzione con formula

(intero più vicino).

Se consideriamo il tempo necessario per l'elevamento a potenza come costante (...) allora

T(n) ε O(1)

Quando un problema ammette diversi algoritmi risolutivi è necessario individuare, e utilizzare, quello con complessità minima...

Se riusciamo a dimostrare che non può esistere un algoritmo con complessità ancora più bassa allora abbiamo individuato la complessità del problema.

Complessità di "Fibonacci" - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito