汉诺塔问题时间复杂度推导

汉诺塔问题

汉诺塔(台港:河内塔)(Tower of Hanoi)是根据一个传说形成的数学问题[1]https://zh.wikipedia.org/wiki/汉诺塔

有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:

  • 每次只能移动一个圆盘;
  • 大盘不能叠在小盘上面。

提示:可将圆盘临时置于 B 杆,也可将从 A 杆移出的圆盘重新移回 A 杆,但都必须遵循上述两条规则。

求解

  • 考虑最简单的情况,只有一个圆盘,此时直接将圆盘移动到 C 即可。
  • 有两个圆盘时,首先将上面的移动到 B,然后将下面的移动到 C,在将 B 上的移动到 C
  • 有3个圆盘时,可以设想如果最下面的那个不存在,那么问题就等于只有2个圆盘了,只不过此时不把这两个圆盘移动到C,而是借助C移动到B上,然后将A上的第三个圆盘移动到C,在借助A将B上的移动到C
  • 因此,有 $n$ 个圆盘时,将问题分解为 $n-1$ 和 第 $n$ 个,首先借助 C 将 前 $n-1$ 个移动到B,第$n$个移动到C,在借助 A 将 B 的那 $n-1$ 个移动到 C
  • 通过以上分析发现子问题需要做两次(借助C移动到B和借助A移动到C),加上一次 第 n 个移动到 C 的操作,因此存在递推关系 $T(n) = 2T(n-1) + 1$
  • 以上递归关系可知,子问题需要的时间翻倍之后便是此问题需要的时间,那么复杂度为 $\ O(2^n)$
汉诺塔问题

推导

已知 $T(n) = 2T(n-1) + 1$,那么可知

$$
\begin{align}
T(1) & = 2T(0) + 1 = 2^0 + 2^0 - 1\\
T(2) & = 2T(1) + 1 = 2^1 + 2^1 - 1\\
T(3) & = 2T(2) + 1 = 2^2 + 2^2 - 1 \\
…\\
T(n) & = 2T(n-1) + 1 = 2^{n-1} + 2^{n-1} - 1 = 2^n - 1\\
\end{align}
$$

因此

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

代码

参考资料

参考资料
1 https://zh.wikipedia.org/wiki/汉诺塔

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注