3.2 函数的增长

大 $\mathcal{O}$ 记号¶

定义：

通俗地说，大 $\mathcal{O}$ 记号是一种数学符号，用于描述函数在变量趋近于某个特定值或无穷大时的极限行为。

令 $f$ 和 $g$ 为从整数集或实数集到实数集的函数。如果存在常数 $C$ 和 $k$ 使得只要当 $x > k$ 时就有
$$ |f(x)| \leqslant C|g(x)| $$
我们就说 $f(x)$ 是 $O(g(x))$ 的。【这个可以读作“$f(x)$ 是大 $Og(x)$ 的”。】

如果$f(x)$是$O(g(x))$的，且$g(x)$是$O(f(x))$的，那么$f(x)$和$g(x)$具有相同阶数（增长速率）。
传递性

如果$f(x)$是$O(g(x))$的，且$g(x)$是$O(h(x))$的，那么$f(x)$是$O(h(x))$的。

一些重要函数的大 $\mathcal{O}$ 估算¶

复合定理

假设 $f(x)$ 是 $O(g(x))$ 且 $\lim_{x \to \infty} h(x) = \infty.$

那么 $(f \circ h)(x)$ 是 $O((g \circ h)(x))$.

示例. 设 $f(n) = \sum_{i=1}^n i^2$，则 $f(n)$ 是 $O(n^3)$.

$\sum_{i=1}^{2^n} i^2$ 是 $O(8^{n})$

$\sum_{i=1}^{2^{2^n}} i^2$ 是 $O(8^{2^n})$
多项式定理

设 $f(x) = a_k x^k + a_{k-1} x^{k-1} + \cdots + a_1 x + a_0$，其中 $a_0, \ldots, a_k \in \mathbb{R}$ 且 $a_k > 0$。
那么 $f(x)$ 是 $O(x^k)$ 且 $x^k$ 是 $O(f(x))$。

可推论到 离散数列
函数增长率层次结构 $$ 1 < log(n)<n<n log(n) < n^2 < 2^n < n! $$
命题：

假设 $f_1(x)$ 是 $O(g_1(x))$，且 $f_2(x)$ 是 $O(g_2(x))$。则 $(f_1 + f_2)(x)$ 是 $O(\max(|g_1(x)|, |g_2(x)|))$。
命题：

假设 $f_1(x)$ 是 $O(g_1(x))$，且 $f_2(x)$ 是 $O(g_2(x))$。则 $(f_1 f_2)(x)$ 是 $O(g_1(x)g_2(x))$。

大$\Omega$与大$\Theta$记号¶

定义1：

令 $f$ 和 $g$ 为从整数集合或实数集合到实数集合的函数。如果存在正常数 $C$ 和 $k$ 使得当 $x > k$ 时有

\[ |f(x)| \geqslant C|g(x)| \]

我们说 $f(x)$ 是 $\Omega(g(x))$ 的（这个读作“$f(x)$ 是大 $\Omega g(x)$ 的”）。

定义2：

如果 $f(x)$ 是 $O(g(x))$ 的且 $f(x)$ 是 $\Omega(g(x))$的，则称 $f(x)$ 是 $\Theta(g(x))$的。

如果 $f(x)$ 是 $\Theta(g(x))$的，则我们说 $f(x)$ 是 $g(x)$ 的同阶的，或者 $f(x)$ 和 $g(x)$ 是同阶的。

$f(x)$ 是 $\Theta(g(x))$的当且仅当：

$f(x)$ 是 $O(g(x))$的且 $g(x)$ 是 $O(f(x))$的；
存在常数 $C_1$、$C_2$ 和 $x_0 \in \mathbb{R}_+$，使得对于所有 $x \geq x_0$，有：$C_1 |g(x)| \leq |f(x)| \leq C_2 |g(x)|$

案例

设 $f(x) = 3x^2 + 8x \log x$。显然，$x^2$ 是 $O(f(x))$。此外，$f(x)$ 是 $O(\max(x^2, x \log x)) = O(x^2)$。因此，$f(x)$ 是 $\Theta(x^2)$。
设 $f(x) = a_k x^k + a_{k-1} x^{k-1} + \cdots + a_1 x + a_0$，其中 $a_0, \ldots, a_k \in \mathbb{R}$ 且 $a_k > 0$。则 $f(x)$ 是 $\Theta(x^k)$。

3.2 函数的增长

大 \(\mathcal{O}\) 记号¶

一些重要函数的大 \(\mathcal{O}\) 估算¶

大\(\Omega\)与大\(\Theta\)记号¶