大O表示法
描述算法复杂度渐进上界的数学记号，用于简洁表达算法效率随输入规模增长的趋势。
定义
Big O 记号的数学定义：
$O(g(n))$ = { $f(n)$: 存在正常量 $c$ 和 $n_0$ ，使得对所有 $n ≥ n_0$ ，有 $0 ≤ f(n) ≤ c*g(n)$ }
$O$（大写字母 O）代表一个函数集合。$O(n^2)$ 代表由 $g(n) = n^2$ 派生的函数集合；说算法复杂度为 $O(n^2)$ 意味着描述该算法的复杂度函数属于此集合。
核心特性
1. 只保留增长速率最快的项
乘法和加法中的常数因子可忽略：
| 原式 | 简化后 |
|---|---|
| O(2N + 100) | O(N) |
| O(2^(N+1)) | O(2^N) |
| O(M + 3N + 99) | O(M + N) |
| O(N³ + 999N² + 999N) | O(N³) |
| O((N+1)*2^N) | O(N*2^N) |
⚠️ 注意：指数中的常数不能消，O(2^(2N)) = O(4^N)
2. 大O表示法表示复杂度的上界
- O(N) 算法也可以说成 O(N²)，理论正确但上界不够"紧"
- 对于输入相关的算法，按最坏情况近似处理是合理的
- 示例：凑零钱递归（K 种硬币，金额 N）→ 最坏情况 O(K^N)
有时候不同人估算的复杂度不同，可能都是对的，只是精度不同。
常见复杂度对照
| 记号 | 名称 | 示例算法 |
|---|---|---|
| O(1) | 常数级 | 哈希表查询、数组随机访问 |
| O(logN) | 对数级 | 二分查找、平衡二叉搜索树操作 |
| O(N) | 线性级 | 单次遍历、线性搜索 |
| O(NlogN) | 对数线性 | 归并排序、快速排序（平均） |
| O(N²) | 平方级 | 冒泡排序、嵌套循环 |
| O(N³) | 立方级 | 三重嵌套循环 |
| O(K^N) | 指数级 | 递归穷举（K 为分支数） |
| O(N!) | 阶乘级 | 全排列 |
与其他渐进记号对比
| 记号 | 含义 | 说明 |
|---|---|---|
| O(g(n)) | 渐进上界 | 复杂度不超过 g(n) |
| Ω(g(n)) | 渐进下界 | 复杂度不低于 g(n) |
| Θ(g(n)) | 渐进紧确界 | 复杂度等于 g(n) |
实战应用
递归算法复杂度估算
以凑零钱问题为例：
- 金额 N，硬币种类 K
- 递归树：K 叉树，最坏高度 N
- 节点数（满 K 叉树）：(K^N - 1)/(K - 1) = O(K^N)