|
Complessità di "Hanoi" |
   |
|
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
| ||||||||||||||||||||||||||||||
|