我最近在解决汉诺塔问题。我使用了“分而治之”的策略来解决这个问题。我将主要问题分成三个较小的子问题，因此产生了以下重现。
T(n)=2T(n-1)+1
解决这个问题会导致
O(2^n) [exponential time]
然后我尝试使用内存技术来解决它，但是这里的空间复杂度也是指数级的，堆空间很快就会耗尽，对于更大的 n 问题仍然无法解决。
有没有办法在小于指数时间的时间内解决问题？解决问题的最佳时间是什么时候？
最佳答案
这取决于您所说的“已解决”是什么意思。 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
关于algorithm - 汉诺塔的复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12383044/