河内塔楼的复杂性？

河内塔楼的复杂性？

这取决于您“已解决”的意思。具有3个钉子和

n

磁盘的河内塔问题需要采取

2**n -1

行动解决，因此，如果要枚举举动，显然不能比

O(2**n)

列举

k

事情做得更好

O(k)

。

另一方面，如果您只想知道所需的移动次数（无需枚举），则计算

2**n - 1

速度会更快。

同样值得注意的是，可以通过

O(n)

以下方式（空间

disk1

最小的磁盘）来反复进行移动枚举（这是最小的磁盘）：

while true:    if n is even:        move disk1 one peg left (first peg wraps around to last peg)    else:        move disk1 one peg right (last peg wraps around to first peg)    if done:        break    else:        make the only legal move not involving disk1