灯前目力虽非昔，犹课蝇头二万言。

# 渐近记号的含义

# $\Theta$ 记号

对于一个给定的函数 $g(n)$, 以 $\Theta (g(n))$ 表示存在 $c_1,c_2 \in \mathbb{R}_+$ 及 $n_0\in\mathbb{N}_+$, 使得对所有的$n≥n_0$ 都有$0≤c_1g(n)≤f(n)≤c_2g(n)$ 的函数 $f(n)$ 组成的集合。这时，我们称 $g(n)$ 是 $f(n)$ 的一个渐近紧确界 (asymptotically tight bound)。

# $O$ 记号

对于一个给定的函数 $g(n)$, 以 $O(g(n))$ 表示存在$c\in \mathbb{R}_+$ 及$n_0\in\mathbb{N}_+$, 使得对所有的$n≥n_0$ 都有$0≤f(n)≤cg(n)$ 的函数 $f(n)$ 组成的集合。此时，称$g(n)$ 是$f(n)$ 的一个渐近上界。

# $\Omega$ 记号

对于一个给定的函数 $g(n)$, 以 $Ω(g(n))$ 表示存在 $c\in \mathbb{R}_+$ 及 $n_0\in\mathbb{N}_+$, 使得对所有的 $n≥n_0$ 都有 $0≤cg(n)≤f(n)$ 的函数 $f(n)$ 组成的集合。此时，称 $g(n)$ 是 $f(n)$ 的一个渐近下界。

# $o$ 记号

对于一个给定的函数 $g(n)$, 以 $o(g(n))$ 表示对任意$c\in \mathbb{R}_+$, 存在$n_0\in\mathbb{N}_+$, 使得对所有的$n≥n_0$ 都有 $0≤f(n)<cg(n)$ 的函数 $f(n)$ 组成的集合。也即$\displaystyle \lim_{n→\infty}\frac{f(n)}{g(n)} = 0$。此时，我们说$o$ 记号表示一个非渐近紧确的上界，并称$f(n)$ 渐近小于$g(n)$。

# $\omega$ 记号

对于一个给定的函数 $g(n)$, 以 $o(g(n))$ 表示对任意$c\in \mathbb{R}_+$, 存在$n_0\in\mathbb{N}_+$, 使得对所有的$n≥n_0$ 都有$0≤cg(n)<f(n)$ 的函数 $f(n)$ 组成的集合。也即$\displaystyle \lim_{n→\infty}\frac{f(n)}{g(n)} = \infty$。我们说$ω$ 记号表示一个非渐近紧确的下界，并称$f(n)$ 渐近大于$g(n)$。

# 渐进记号的性质

对渐近记号，我们不加证明地说明几个性质。$Θ$, $O$ 和 $Ω$ 记号满足自反性。所有五个渐近记号都满足传递性。仅 $\Theta$ 记号满足对称性。此外，我们有 $f(n)=O(g(n)) \Leftrightarrow g(n) =Ω(f(n))$ 及 $f(n) = o(g(n)) \Leftrightarrow g(n) = ωf(n)$, 我们称这个性质为转置传递性。