算法复杂度
一、时间规模的直觉
| 事件 | 时间 | 量级 |
|---|---|---|
| 宇宙大爆炸至今 | ~138 亿年 | $10^{21}$ sec = $10 \times (10^{10})^2$ |
| “三生三世” | ~300 年 | $10^{10}$ sec |
| 100 年 | $3 \times 10^9$ sec | |
| 1 天 | 24 小时 | $10^5$ sec |
二、复杂度层级
| 类型 | 记号 | 说明 |
|---|---|---|
| 常数 | $O(1)$ | 与输入规模无关 |
| 对数 | $O(\log n)$ | 见下方换底/幂次性质 |
| 线性 | $O(n)$ | |
| 幂 | $O(n^c)$ | |
| 指数 | $O(a^n)$ | 不可忍受 |
对数复杂度的两个性质
换底公式：$\log_a n = \log_a b \cdot \log_b n$，其中 $\log_a b$ 是常数，所以对数底数在 $O$ 记号中无所谓
幂次法则：$\log(n^c) = c \cdot \log n$，其中 $c$ 是常数，所以 $O(\log n^c) = O(\log n)$
三、等比级数求和实例
\[T(n) = O(1) \cdot (2^0 + 2^1 + 2^2 + \cdots + 2^{\log n}) = O(1) \cdot (2^{\log n + 1} - 1) = O(n)\]理解 等比级数 $1 + 2 + 4 + \cdots + n$ 的和约为 $2n$，所以整体复杂度还是 $O(n)$，不会因为逐层倍增而”爆炸”。