渐近记号

概述

渐近记号是描述函数增长率之间关系的数学工具统称，包括 $O$ 、 $Ω$ 、 $Θ$ 、 $o$ 、 $ω$ 五种记号。

定义

五种渐近记号

$O$ 记号：渐近上界 — 大O记号

$Ω$ 记号：渐近下界 — 大Omega记号

$Θ$ 记号：渐近紧界 — 大Theta记号

$o$ 记号：严格上界（非渐近紧）

$ω$ 记号：严格下界（非渐近紧）

$f (n) = Θ (g (n))$ 当且仅当 $f (n) = O (g (n))$ 且 $f (n) = Ω (g (n))$ 。
$o$ 与 $ω$ 类似于 $O$ 与 $Ω$ ，但不允许等号（严格不等式），极限形式： $lim_{n \to \infty} f (n) / g (n) = 0$ （ $o$ ）或 $\infty$ （ $ω$ ）。
渐近记号可嵌套使用，如 $O (n l g n + n^{2}) = O (n^{2})$ 。
传递性：若 $f = O (g)$ 且 $g = O (h)$ ，则 $f = O (h)$ 。