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

ComplessitÓ di "Fibonacci"

Precedente
SUPERIORE
Successiva

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 = 22-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 = 23-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 = 24-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 = 25-1
...

Quindi

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)

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) = c1+c2n ε 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

Precedente
SUPERIORE
Successiva