大O记号

概述

大O记号给出函数的渐近上界，是最常用的算法复杂度描述工具。

定义

大O记号

$O (g (n)) = {f (n) : \exists c > 0, \exists n_{0} > 0, 使得 0 \leq f (n) \leq c \cdot g (n), \forall n \geq n_{0}}$ 读作 ” $f (n)$ 是 $g (n)$ 的大O”。

$O (g (n))$ 是一个函数集合，习惯上写 $f (n) = O (g (n))$ 而非 $f (n) \in O (g (n))$ 。
$O$ 记号给出的是上界，不一定是紧界： $n = O (n^{2})$ 成立，但 $n^{2}$ 不是 $n$ 的紧界。
常见等式： $O (1)$ （常数）、 $O (l g n)$ （对数）、 $O (n)$ （线性）、 $O (n l g n)$ （线性对数）、 $O (n^{2})$ （二次）、 $O (2^{n})$ （指数）。
极限判别：若 $lim_{n \to \infty} f (n) / g (n)$ 存在且有限，则 $f (n) = O (g (n))$ 。