注：文中斜体的文字表示我自己的想法或阐发，不一定严谨或正确。
大 O 记号
定义 1 称函数 \(f(x) = \mathcal{O}(g(x))\)，当且仅当存在正常数 \(k, C\)，使得只要 \(x > k\)，就有 \(|f(x)| \leq C|g(x)|\) 成立.
例 1 证明 \(x^2 + 2x + 1 = \mathcal{O}(x^2)\).
解 设 \(f(x) = x^2 + 2x + 1, g(x) = x^2\)，并令 \(k = 1\)，则当 \(x > 1\) 时有
\[ \begin {align*} \ \left| f(x) \right| & = f(x) = x^2 + 2x + 1 \\ & \leq x^2 + 2x^2 + x^2 = 4x^2 = 4 \left| g(x) \right|. \end {align*} \] 即我们找到了正常数 \(k = 1, C = 4\)，使得只要 \(x > k\)，就有 \(|f(x)| \leq C|g(x)|\). 因此 \(x^2 + 2x + 1 = \mathcal{O}(x^2)\). \(\Box\)
用极限的语言，我们有下述定理：
定理 1（大 O 比率定理） 如果极限 \(\lim\limits_{x\to\infty} \left| \frac{f(x)}{g(x)} \right|\) 存在，则 \(f(x) = \mathcal{O}(g(x))\).
证 若极限 \(\lim\limits_{x\to\infty} \left| \frac{f(x)}{g(x)} \right|\) 存在且等于 \(l\)，按极限的定义有 \[ \begin {align*} & \forall \epsilon > 0, \exists N(x > N \to \left| \left| \frac{f(x)}{g(x)} \right| - l \right| < \epsilon) \\ \implies & \forall \epsilon > 0, \exists N(x > N \to \left| \frac{f(x)}{g(x)} \right| - \left| l \right| < \epsilon) \\ \iff & \forall \epsilon > 0, \exists N(x > N \to \left| \frac{f(x)}{g(x)} \right| < \epsilon + \left| l \right|) \\ \iff & \forall \epsilon > 0, \exists N(x > N \to \left| \frac{f(x)}{g(x)} \right| < C) \end {align*} \] 其中 \(C = \epsilon + \left| l \right|\). 则存在正常数 \(N, C\)，使得只要 \(x > N\)，就有 \(|f(x)| < C|g(x)|\) 成立，从而 \(f(x) = \mathcal{O}(g(x))\). \(\Box\)
注意，取 \(g(x) \equiv 1\) 时，即函数 \(f(x) = \mathcal{O}(1)\) 时，有 \(\forall x (x > k \to |f(x)| \leq C)\)，这就是函数有界性的定义.
若 \(f(x), g(x)\) 都是 \(x\to\infty\) 时的无穷大，则 \(f(x) = \mathcal{O}(g(x))\) 意味着随着 \(x\) 无限增长，\(f(x)\) 趋于无穷大的“速度”（即阶）不高于 \(g(x)\)，其中阶（order）是指数量级（order of magnitude）. 换言之，当 \(x\) 充分大时，\(g(x)\) 是 \(f(x)\) 增长率的上界.
时间复杂度
一个算法的基本操作是该算法中我们感兴趣的、重复执行次数最多的操作. 我们把算法的具体实现中基本操作所对应语句的执行次数称为该语句的频度. 有些时候，基本操作语句的频度是一个常数，而与算法输入数据的大小（问题规模）无关；更多时候，频度是问题规模 \(n\) 的函数 \(f(n)\). 例如，求 \(1 + 2 + \dots + n\)，如果我们用笨办法一个个加，显然算法的基本操作是加法运算（并赋值），总共要执行 \(n - 1\) 次，即 \(f(n) = n - 1\)；但如果我们用等差数列求和公式，则只需一条语句就可求出结果，不需要重复执行，频度为 \(1\)，不管所给的 \(n\) 多大，都只用执行一次即可.
我们可以用大 O 记号来刻画算法执行时间随问题规模增长而增长的速度，从而对算法的效率有个大致的把握. 设问题规模为 \(n\)，算法基本操作语句的频度为 \(f(n)\)，若 \(f(n) = \mathcal{O}(g(n))\)，则我们可以说该算法的时间复杂度为 \(\mathcal{O}(g(n))\)（一般 \(g(n)\) 会是较 \(f(n)\) 简洁的函数）. 如上求和算法的例子中，笨办法的时间复杂度为 \(\mathcal{O}(n)\)（易证 \(n - 1 = \mathcal{O}(n)\)），而公式法的时间复杂度为 \(\mathcal{O}(1)\). 一般地，我们有
\[ \begin {align*} \mathcal{O}(1) & \subset \mathcal{O}(\log n) \subset \mathcal{O}(n) \subset \mathcal{O}(n \log n) \\ & \subset \mathcal{O}(n^2) \subset \mathcal{O}(n^k)(k>2) \subset \mathcal{O}(2^n) \end {align*} \] 这里用了包含符号，因为 \(\mathcal{O}(g(x))\) 事实上是同样复杂度函数的集合，\(f(x) = \mathcal{O}(g(x))\) 严格来说也应该写成 \(f(x) \in \mathcal{O}(g(x))\)，但前者已经约定俗成了.
上述式子可通俗地理解为，随着问题规模无限增长，时间复杂度为常数阶 \(\mathcal{O}(1)\) 的算法所需的执行时间增长不快于对数阶 \(\mathcal{O}(\log n)\) 的，对数阶的不快于线性阶 \(\mathcal{O}(n)\) 的，线性阶的不快于线性对数阶 \(\mathcal{O}(n \log n)\) 的，线性对数阶的不快于平方阶 \(\mathcal{O}(n^2)\) 的，平方阶的不快于多项式阶 \(\mathcal{O}(n^k)\) 的，多项式阶的不快于指数阶 \(\mathcal{O}(2^n)\) 的. 换句话说，上述时间复杂度所代表的算法效率依次递减. 在实际的算法设计中，一般认为时间复杂度为多项式阶 \(\mathcal{O}(n^k)\)（及更快）的算法是可接受的，指数阶 \(\mathcal{O}(2^n)\) 的算法则是不可接受的，因为一旦问题规模增大，其所需执行时间指数爆炸式增长.
一些运算规则
由大 O 记号的定义可证明以下运算规则： \[ \begin {array} \ \mathcal{O}(f(x)) + \mathcal{O}(g(x)) = \mathcal{O}(\max(f(x), g(x))) \\ \mathcal{O}(f(x)) \cdot \mathcal{O}(g(x)) = \mathcal{O}(f(x) \cdot g(x)) \\ \mathcal{O}(cf(x)) = \mathcal{O}(f(x)) (c \neq 0) \\ f(x) = \mathcal{O}(g(x)) \implies cf(x) = \mathcal{O}(g(x)). \end {array} \]
