在河内塔问题中，将钉子数量从 3 增加到 4,5，时间复杂度会有任何变化吗？

Question

如果河内塔有4个钉子，而不是传统的河内塔有3个钉子，代码（cpp）的时间复杂度会有什么变化，这是一个数据结构和算法问题，唯一的变化是答案是，如果有 4 个钉子，移动次数会减少，对吗？

我预计传统的河内塔和带有 4 个钉子的 TOH 的代码的时间复杂度不会发生变化。

Answer 1

Frame-Stewart 算法，被认为对于任意数量的钉子都是最佳的，其复杂度为

2^Θ(n^1/(r−2))

（链接页面中的公式看起来更整洁）。

如果算法的输入是磁盘数量 (

n

) 并且您将钉子数量 (

r

) 固定为任何值（只要将其固定为 1），那么它就是

O(2^n)

确实是时间复杂度。