二分查找的时间复杂度为什么是O(logn)

直接推导

设问题规模为 $n$,需要 $t$ 次查找,由二分查找的过程可知,每一次查找问题规模减半,最差情况下,直到问题规模为 1 时才找到或者仍未找到,因此可知:

$$n \times \left(\frac{1}{2}\right) ^t = 1$$

则:

$$2^t = n$$

两边取 $\log$,得

$$t = \log_{2}{n}$$

主定理

在算法分析中,支配理论(英语:master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery,Dorothea Haken和James B. Saxe在1980年提出,在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen,Leiserson,Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知[1]https://zh.wikipedia.org/wiki/主定理。不过,并非所有递推关系式都可应用支配理论

假设有递归关系式 $T(n) = aT\left(\dfrac{n}{b}\right) + f(n)$,其中 $a \geq 1 \mbox{, } b > 1$,其中,$n$为问题规模,$a$为递归的子问题数量,$\dfrac{n}{b}$为每个子问题的规模(假设每个子问题的规模基本一样),$f(n)$为递归以外进行的计算工作。

$f(n)$ 为函数,$T(n)$ 为非负整数,则有以下结果(分类讨论):

  1. 如果存在常数$\epsilon > 0$,有 $f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$(可不严谨的視作多项式地小于)则 $T(n) = \Theta\left( n^{\log_b a} \right)$
  2. 如果存在常数$\epsilon\ge0$,有 $f(n) = \Theta\left( n^{\log_b a} \log^{\epsilon} n \right)$ 则 $T(n) = \Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right)$
  3. 如果存在常数$\epsilon > 0$,有 $f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right)$(多项式地大于) 同时存在常数$c < 1$以及充分大的$n$,满足 $a f\left( \dfrac{n}{b} \right) \le c f(n)$ 则 $T\left(n \right) = \Theta \left(f \left(n \right) \right)$

简化版主定理

由于主定理公式十分复杂,计算时可以使用简化版本[2]https://hunterhug.github.io/goa.c/#/basic/master_method

若算法的运行时间 $T(n) \le aT\left(\dfrac{n}{b}\right) + \ O(n^d)$,其中 $a \ge 1$ 是子问题个数,$b \ge 1$是输入规模减小的倍数,$d \ge 0$ 是递归过程之外的步骤的时间复杂度指数,则:

$$T\left(n\right) = \begin{cases}
\ O\left(n^d\log{}{n}\right) & a = b^d
\\
\ O\left(n^d\right) & a \lt b^d
\\
\ O\left(n^{\log_{b}{a}}\right) & a \gt b^d
\end{cases}$$

主定理应用

算法abd情况复杂度
二分查找120$a = b^{d}$$\ O(\log{}{n})$
快速排序221(计算分区索引的复杂度为$\ O(n)$)$a = b^{d}$$\ O(n\log{}{n})$
归并排序221 (合并操作的复杂度为 $\ O(n)$)$a = b^{d}$$\ O(n\log{}{n})$
主定理应用

logn算法的优势

算法时间复杂度对比
算法时间复杂度对比

可以看到差距非常大,随着问题规模增大,$\log_{2}{n}$ 算法增长的非常缓慢。$2^{10} = 1024$, $2^{20} \approx 100 0000$,问题规模 100 万的时候,$\ O(n)$ 算法需要 100万次,而 $\ O(\log{}{n})$ 只需要 20 次。

参考资料

参考资料
1 https://zh.wikipedia.org/wiki/主定理
2 https://hunterhug.github.io/goa.c/#/basic/master_method

发表评论

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