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