shr*_*sva 1 algorithm towers-of-hanoi
我如何解决河内塔问题的运行时间.我得到一个像t(n)= 2t(n-1)+ 1的递归反射.绘制递归树后,我得到每一步的值,如1 + 2 + 4 + 8 ...树的高度将是lg (N).我如何计算系列的总和？我什么时候停止？
你在递归树的每个级别获得的是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.