Complessità: torre di Hanoi

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti dei dischi

T(1)=1
T(2)=T(1)+T(1)+T(1)=3
T(3)=T(2)+T(1)+T(2)=7
T(4)=T(3)+T(1)+T(3)=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 risolvere il problema sono

n T(n)=2n-1 1 Hz
(uomo)
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!
Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità: torre di Hanoi

Comments are closed.