algorithm - 汉诺塔问题的解决方案

Question

我如何解决汉诺塔问题的运行时间。我得到一个像 t(n) = 2t(n-1) + 1 这样的递归关系。在绘制递归树之后，我在每一步都得到像 1+2+4+8 这样的值...树的高度将是 lg (n).我如何计算系列的总和？我什么时候停止？

Answer 1

你在递归树的每一层得到的是 2 的幂。因此，总和是:2^0 + 2^1 + 2^2 + ... + 2^{n-1 。

这是一个几何和:http://en.wikipedia.org/wiki/Geometric_progression

令 S(n) = 1 + 2 + 4 + ... + 2^{n-1}。然后:S(n) - 2*S(n) = 1 - 2^n

最后:S(n) = 2^n - 1。