上一篇提到，并非所有递推关系式都可应用支配理论。那么，递归求阶乘的算法可以用吗？ 递归求阶乘算法 算法如下 计算过程是 $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 →