Asymptotic Analysis---渐近符号总结

渐近符号总结

在学习算法的时候，一个很重要的部分就是复杂度分析，或者说是叫做渐进分析，本文简单总结了相应的符号的意思。

1. Big O - $O(g(n))$ - 上界 (Upper Bound)

• 定义: $f(n) = O(g(n))$ 当且仅当存在常数 $c > 0$ 和 $n_0$，使得对于所有 $n \geq n_0$：

  $$f(n) \leq c \cdot g(n)$$

• 含义: $f(n)$ 的增长不会超过 $g(n)$（最坏情况）

• 例子: $3n^2 + 5n = O(n^2)$，也可以说 $= O(n^3)$（但不够紧）

---

2. Big Omega - $\Omega(g(n))$ - 下界 (Lower Bound)

• 定义: $f(n) = \Omega(g(n))$ 当且仅当存在常数 $c > 0$ 和 $n_0$，使得对于所有 $n \geq n_0$：

  $$f(n) \geq c \cdot g(n)$$

• 含义: $f(n)$ 的增长至少是 $g(n)$（最好情况的下界）

• 例子: $3n^2 + 5n = \Omega(n^2)$，也可以说 $= \Omega(n)$（但不够紧）

---

3. Big Theta - $\Theta(g(n))$ - 紧界 (Tight Bound)

• 定义: $f(n) = \Theta(g(n))$ 当且仅当 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$

  即存在常数 $c_1, c_2 > 0$ 和 $n_0$，使得对于所有 $n \geq n_0$：

  $$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$$

• 含义: $f(n)$ 和 $g(n)$ 的增长率相同

• 例子: $3n^2 + 5n = \Theta(n^2)$

---

4. Little o - $o(g(n))$ - 严格上界 (Strict Upper Bound)

• 定义: $f(n) = o(g(n))$ 当且仅当对于任意常数 $c > 0$，存在 $n_0$ 使得对于所有 $n \geq n_0$：

  $$f(n) < c \cdot g(n)$$

  等价于: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

• 含义: $f(n)$ 增长严格慢于 $g(n)$

• 例子: $n = o(n^2)$，但 $n^2 \neq o(n^2)$

---

5. Little omega - $\omega(g(n))$ - 严格下界 (Strict Lower Bound)

• 定义: $f(n) = \omega(g(n))$ 当且仅当对于任意常数 $c > 0$，存在 $n_0$ 使得对于所有 $n \geq n_0$：

  $$f(n) > c \cdot g(n)$$

  等价于: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

• 含义: $f(n)$ 增长严格快于 $g(n)$

• 例子: $n^2 = \omega(n)$，但 $n^2 \neq \omega(n^2)$

---

总结表格

符号	含义	类比
$f = O(g)$	$f \leq c \cdot g$	$\leq$
$f = \Omega(g)$	$f \geq c \cdot g$	$\geq$
$f = \Theta(g)$	$c_1 g \leq f \leq c_2 g$	$=$
$f = o(g)$	$f < c \cdot g$ (任意$c$)	$<$
$f = \omega(g)$	$f > c \cdot g$ (任意$c$)	$>$

---

常见增长率排序（从慢到快）

$$1 < \log n < \sqrt{n} < n < n \log n < n^2 < n^3 < 2^n < n! < n^n$$