时间复杂度
为什么关注最坏情况
- 最坏情况给出了算法执行时间的上界，我们可以确信，无论给什么输入，算法的执行时间都不会超过这个上界，这样为比较和分析提供了便利。
- 对于某些算法，最坏情况是最常发生的情况，例如在数据库中查找某个信息的算法，最坏情况就是数据库中根本不存在该信息，都找遍了也没有，而某些应用场合经常要查找一个信息在数据库中存在不存在。
- 虽然最坏情况是一种悲观估计，但是对于很多问题，平均情况和最坏情况的时间复杂度差不多，比如插入排序，平均情况和最坏情况的时间复杂度都是输入长度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）求解递归式分为两步：
- 猜测解的形式；
- 用数学归纳法求出解的常数，并证明解是正确的。
可以简洁地证明一个解是递归式的正确解，但想出一个好的猜测可能很困难。
递归树法
在递归树（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)\]
