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

ComplessitÓ di "Hanoi"

Precedente
SUPERIORE
Successiva

L'algoritmo ricorsivo Ŕ

procedure Hanoi(N, Origine, Libero, Arrivo: Byte);
begin
   if(N = 1) then
      write(Origine:2, ' --> ', Arrivo:2)
   else
      begin
         Hanoi(N-1, Origine, Arrivo , Libero);
         Hanoi(1  , Origine, Libero , Arrivo);
         Hanoi(N-1, Libero , Origine, Arrivo);
      end;
end;

Il tempo di attesa Ŕ dato dal numero di chiamate ricorsive (mosse...)

T(1) = 1
T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3 = 22-1
T(3) = T(2)+T(1)+T(2) = 2*T(2)+1 = 2*3+1 = 7 = 23-1
T(4) = ... = 2*7+1 = 15 = 24-1
...

Per induzione, se

T(1) = 1

e

T(n-1) = 2n-1-1

allora

T(n) = 2*T(n-1)+1
     = 2(2n-1-1)+1
     = 2n-2+1
     = 2n-1.

Il problema della torre di Hanoi ha complessitÓ O(2n), esponenziale, e qualunque altro algoritmo risolutivo non potrÓ avere complessitÓ minore... (Ŕ un problema intrinsecamente esponenziale)

I tempi necessari per risolvere il problema sono

nT(n) = 2n-1Tempi
1 Hz (uomo)1 GHz (PC)
121-1 = 1un secondo10-9 s
222-1 = 33 secondi3*10-9 s
10210-1 = 1023~17 minuti~10-6 s
20220-1 = 1.048.575~12 giorni~10-3 s
30230-1 = 1.073.741.823~34 anni~1 s
64264-1 = 18.446.744.073.709.551.615~5*1011 anni~500 anni

ComplessitÓ di "Hanoi" - ApPuNtIdIuNiNfOrMaTiCo

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

Precedente
SUPERIORE
Successiva