汉诺塔问题 汉诺塔（台港：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题[1]https://zh.wikipedia.org/wiki/汉诺塔： 有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆： 每次只能移动一个圆盘； 大盘不能叠在 … Continue reading →

上一篇提到，并非所有递推关系式都可应用支配理论。那么，递归求阶乘的算法可以用吗？ 递归求阶乘算法 算法如下 计算过程是 $1 \times 2 \times 3 ... \times n$，基本能直接看出来时间复杂度是 $\ O(n)$。 用主定理求解 在 CSDN 上有一篇文章[1]https://blog.csdn.net/weixi … Continue reading →

直接推导 设问题规模为 $n$，需要 $t$ 次查找，由二分查找的过程可知，每一次查找问题规模减半，最差情况下，直到问题规模为 1 时才找到或者仍未找到，因此可知： $$n \times \left(\frac{1}{2}\right) ^t = 1$$ 则： $$2^t = n$$ 两边取 $\log$，得 $$t = \log_{2} … Continue reading →