为什么关注最坏情况

  1. 最坏情况给出了算法执行时间的上界,我们可以确信,无论给什么输入,算法的执行时间都不会超过这个上界,这样为比较和分析提供了便利。
  2. 对于某些算法,最坏情况是最常发生的情况,例如在数据库中查找某个信息的算法,最坏情况就是数据库中根本不存在该信息,都找遍了也没有,而某些应用场合经常要查找一个信息在数据库中存在不存在。
  3. 虽然最坏情况是一种悲观估计,但是对于很多问题,平均情况和最坏情况的时间复杂度差不多,比如插入排序,平均情况和最坏情况的时间复杂度都是输入长度n的二次函数。

渐进记号

, 和的图例

\(\Theta\) 记号

\(\Theta\) 记号渐进地给出一个函数的上界和下界。若存在正常量 \(c_1\) 和 \(c_2\) ,使得对于足够大的\(n\),函数\(f(n)\)能夹入\(c_{1}g(n)\) 与 \(c_{2}g(n)\)之间,就说 \(f(n)\) 和 \(\Theta(g(n))\) 是同一量级的。我们通常记“\(f(n)=\Theta(g(n))\)”以表达相同的概念。

\(O\) 记号

\(O\)(读作大\(O(g(n))\),有时仅读作\(O(g(n))\))记号给出一个函数的渐进上界。

\(\Omega\) 记号

\(\Omega\) 记号给出一个函数的渐进下界。

\(o\) 记号和 \(\omega\) 记号

另外还有 \(o\) 记号和 \(\omega\) 记号,分别表示一个非渐进紧确的上界和非渐进紧确的下界。

记忆小秘诀

  • \(\Theta\) 的含义和“等于”类似;
  • \(O\) 的含义和“小于或等于”类似;
  • \(\Omega\) 的含义和“大于或等于”类似;
  • \(o\) 的含义和“小于”类似;
  • \(\omega\) 的含义和“大于”类似;

几种常见的时间复杂度

几种常见的时间复杂度函数按数量级从小到大的顺序依次是:

\(\Theta(\lg{n})\),\(\Theta(sqrt(n))\),\(\Theta(n)\),\(\Theta(n\lg{n})\),\(\Theta(n2)\),\(\Theta(n3)\),\(\Theta(2n)\),\(\Theta(n!)\)

求解递归式的复杂度

代入法

代入法(The Substitution Method)求解递归式分为两步:

  1. 猜测解的形式;
  2. 用数学归纳法求出解的常数,并证明解是正确的。

可以简洁地证明一个解是递归式的正确解,但想出一个好的猜测可能很困难。

递归树法

在递归树(Recursion Tree)中,每个节点表示一个单一子问题的代价,子问题对应某次递归函数调用。我们将树中每层中的代价求和,得到每层代价,然后将所有层的代价求和,得到所有层次的递归调用的总代价。

为递归式构造递归树

最适合用来生成好的猜测,然后即可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时,常常需要忍受一点儿“不精确”,因为稍后才会验证猜测是否正确。

主方法

主方法(The Master Method)为如下形式的递归式提供了一种菜谱式的求解方法\[T(n)=aT(n/b)+f(n)\]其中 \(a\le{}1\) 和 \(b\le{}1\) 是常数,\(f(n)\) 是渐近正函数。为了使用主方法,需要牢记三种情况,但随后你就可以很容易地求解很多递归式,通常不需要纸和笔的帮助。

假设有递推关系式

\[T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)\],其中 \(a \geq 1 \mbox{, } b > 1\)

其中,\(n\)为问题规模,\(a\)为递推的子问题数量,\(n/b\)为每个子问题的规模(假设每个子问题的规模基本一样),\(f(n)\)为递推以外进行的计算工作。

情形一:小于

如果存在常数 \(\epsilon > 0\),有

\[f(n) = \color{red}{O}\left( n^{\log_b (a) - \epsilon} \right)\],并且是多项式的 小于

那么

\[T(n) = \Theta\left( n^{\log_b a} \right)\]

情形二:等于

如果存在常数 \(k \ge 0\),有

\[f(n) = \color{red}{\Theta}\left( n^{\log_b a} \log^{k} n \right)\]

那么

\[T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n \right)\]

情形三:大于

如果存在常数 \(\epsilon > 0\),有

\[f(n) = \color{red}{\Omega}\left( n^{\log_b (a) + \epsilon} \right)\],并且是多项式的 大于

同时存在常数\(c < 1\)以及充分大的\(n\),满足

\[a f\left( \frac{n}{b} \right) \le c f(n)\]

那么

\[T\left(n \right) = \Theta \left(f \left(n \right) \right)\]

深入理解

  1. MIT算法导论:渐近符号、递归及解法