知识点复习

重要概念回顾

(1): 大O：当 $x \to a$ 时，称 $f (x) = O (g (x))$ ，若 $\exists M > 0$ ， $\exists \overset{\circ}{U} (a, δ)$ 使得 $x \in \overset{\circ}{U} (a, δ) ⟹ | f (x) | \leq M | g (x) |$ 。
(2): 小o：当 $x \to a$ 时，称 $f (x) = o (g (x))$ ，若 $\forall ε > 0$ ， $\exists \overset{\circ}{U} (a, δ)$ 使得 $x \in \overset{\circ}{U} (a, δ) ⟹ | f (x) | \leq ε | g (x) |$ 。
(3): 有界量：当 $x \to a$ 时，称函数 $f$ 是有界量（即 $f (x) = O (1)$ ），若 $\exists M > 0$ ， $\exists \overset{\circ}{U} (a, δ)$ 使得 $x \in \overset{\circ}{U} (a, δ) ⟹ | f (x) | \leq M$ 。
(4): 不比～更低阶的无穷小、更高阶的无穷小，不比～更低阶的无穷大、更高阶的无穷大。
(5): 同阶：称 $f$ 与 $g$ 同阶，若 $f (x) = O (g (x))$ 且 $g (x) = O (f (x))$ 。
(6): 等价：称 $f$ 与 $g$ 等价，若 $f (x) = g (x) + o (g (x))$ 。

重要定理回顾

(1)

大O与小o的运算性质：

$f = O (f)$ ；一般 $f \notin o (f)$ ，除非在 $c$ 的某个去心邻域中 $f (x) = 0$ 。
$f = o (g) ⟹ f = O (g)$ ，即 $o (g) \subseteq O (g)$ 。一般 $o (g) \neq O (g)$ ，除非 $g (x) = 0$ 。
$f = O (p) \land g = O (q) ⟹ f g = O (p q)$ 。
$f = O (p) \land g = o (q) ⟹ f g = o (p q)$ 。
$o (h)$ 和 $O (h)$ 都是线性空间，即 $f = O (h) \land g = O (h) ⟹ λ f + μ g = O (h)$ ，对 $o$ 成立类似的结论，其中 $λ, μ \in R$ 。

(2)

当 $x \to a$ 时，若 $f (x) + o (f (x)) = G (x) + o (g (x))$ ， $G (x) = O (g (x))$ ，则 $f (x) = G (x) + o (g (x))$ 。

(3)

推论：当 $x \to a$ 时，若 $f (x) = g (x) + o (g (x))$ ，则 $g (x) = f (x) + o (f (x))$ 。

应用

(1): 当 $x \to 0$ 时， $\sin x = x + o (x)$ ， $\cos x = 1 - \frac{x^{2}}{2} + o (x^{2})$ ， $\tan x = x + o (x)$ 。
(2): 当 $x \to 0$ 时， $e^{x} = 1 + x + o (x)$ ， $\ln (1 + x) = x + o (x)$ ， $(1 + x)^{r} = 1 + r x + \frac{r (r - 1)}{2!} x^{2} + o (x^{2})$ 。
(3): 设 $0 < α < β$ 。当 $x \to 0^{+}$ 时， $x^{β}$ 是比 $x^{α}$ 更高阶的无穷小；当 $x \to + \infty$ 时， $x^{β}$ 是比 $x^{α}$ 更高阶的无穷大。

注

(1): 算法理论（如数据结构）中还常用 $Ω, Θ$ 符号。
(2): 有些教材用 “ $f (x) \sim g (x)$ ” 来表示 $f$ 与 $g$ 等价，并提出了无穷小等价替换的做法。我们不建议使用这种方法，请大家在计算过程中始终保留 $o$ 记号。