Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi
- T(1) = 1
- T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3
- T(3) = T(2)+T(1)+T(2) = 3+1+3 = 7
- T(4) = T(3)+T(1)+T(3) = 7+1+7 = 15
- …
- T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1
- …
Numericamente si tratta della successione 1, 3, 7, 15, 31, 63, 127, ... cioè 21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, ... quindi T(n) = 2n-1
I tempi necessari per una persona oppure per un computer sono
| n | T(n) = 2n-1 | 1 Hz (persona) | 1 GHz (PC) | |
|---|---|---|---|---|
| 1 | 21-1 | = 1 | un secondo | 10-9 s |
| 2 | 22-1 | = 3 | 3 secondi | 3*10-9 s |
| 10 | 210-1 | = 1023 | ~17 minuti | ~10-6 s |
| 20 | 220-1 | = 1.048.575 | ~12 giorni | ~10-3 s |
| 30 | 230-1 | = 1.073.741.823 | ~34 anni | ~1 s |
| 64 | 264-1 | = 18.446.744.073.709.551.615 | ~5*1011 anni | ~500 anni |
Conclusioni
- L’algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2n).
- Non può esistere un algoritmo con complessità minore.
- Il problema della torre di Hanoi è un problema intrinsecamente esponenziale.
- Il problema della torre di Hanoi è un problema intrattabile!