汉诺塔算法的复杂度是如何推导的？

为什么是 $2^n$ ？

设移动 $n$ 个需要时间 $T(n)$，首先需要借助 C 将 上面 $n-1$ 个圆盘移动到 B 上面，相当于 n-1 个圆盘借助B移动到C，因此此步骤需要时间 $T(n-1)$，然后将第 $n$ 个圆盘移动到 C，需要时间为 1，然后在借助 A 将 B 上的圆盘移动到C，又是一个 $T(n-1)$，因此：
$$T(n) = 2T(n-1)+1$$
可以看出，每增加一个圆盘，所需时间翻倍，即复杂度为 $2^n$。

推导：
由于 $T(1) = 1$ ，即一个圆盘时只需要移动一次，代入上面的公式，可得
$$T(2) = 2+1 = 2^1 + 2^1-1\\
T(3)  = 2^2 + 2^2-1 \\
...\\
T(n)  = 2^{n-1} + 2^{n-1} -1 = 2^n - 1$$

所以
$$T(n) = 2^n - 1 = \ O(2^n)$$