河内塔楼的复杂性？

  • Z时代
  • 2024-01-10
  • 分类：问答

我最近正在解决河内塔的问题。我使用“分而治之”策略来解决此问题。我将主要问题分为三个较小的子问题，因此产生了以下重复发生。

T（n）= 2T（n-1）+1

解决这个问题导致

O（2 ^ n）[指数时间]

然后我尝试使用记忆技术来解决它，但是这里空间的复杂度也是指数级的，堆空间很快用完，对于较大的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

以上是 河内塔楼的复杂性？ 的全部内容， 来源链接： utcz.com/qa/398371.html

回到顶部