##### 复杂性测量 - 复杂性测量 - **复杂性测量**是对[[计算复杂性]]量化的数学工具, 主要包括大O记号和小o记号, 用于极限分析, 即关注当输入规模趋于无穷大时 $n\to\infty$, 算法的性能表现 - 设函数 $f, g: \mathbb{N} \to \mathbb{R}^+$, 如果存在正整数 $c$ 和 $n_0$, 使得对于所有 $n \geq n_0$, 满足 $f(n) \leq c \cdot g(n)$, 则称 $f(n) = O(g(n))$, 表示$g(n)$ 是 $f(n)$ 的渐进上界 - 设函数 $f, g: \mathbb{N} \to \mathbb{R}^+$, 如果极限 $\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, 则称 $f(n) = o(g(n))$, 表示 $f(n)$ 的增长速度严格小于 $g(n)$