河内塔的复杂性？

Question

我最近解决了河内塔问题.我用"分而治之"策略来解决这个问题.我将主要问题分成了三个较小的子问题,因此产生了重复发生.

T(N)= 2T(N-1)+1

解决这个问题导致

O(2 ^ n)[指数时间]

然后我尝试使用memoization技术来解决它,但是这里空间复杂度也是指数级的,并且堆空间很快耗尽,并且对于较大的n,问题仍然无法解决.

有没有办法在不到指数的时间内解决问题？什么是解决问题的最佳时间？

Answer 1

您可以解决重复发生并获得封闭形式.

T(n)= 2*T(n-1)+ 1

T(n)= 2*(2*T(n-2)+ 1)+ 1

T(n)=(2 ^ 2)*T(n-2)+ 2 ^ 1 + 2 ^ 0

T(n)=(2 ^ k)*T(nk)+ 2 ^(k-1)+ 2 ^(k-2)+ ... + 2 ^ 0

解决这个问题就此结束了

T(n)=(2 ^ n)-1,T(0)= 0

现在通过平方使用取幂.

Answer 2

这取决于你所说的"解决".河内塔的问题有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