为什么先做复杂度分析
渐进分析回答的是“输入变大时成本如何放大”。它比常数项调优更能决 定算法是否可扩展。
定义
Big-O 上界
表示存在常数 与 ，使得对所有 都有 。
边读边试
在同一 n 比较渐进增长
在同一 n 下比较多种级别，让相对增长差距具体化。
| Class | Value at n=16 |
|---|---|
| O(1) | 1.00 |
| O(log n) | 4.00 |
| O(n) | 16.00 |
| O(n log n) | 64.00 |
| O(n^2) | 256.00 |
常见级别
O(1)：直接存取、已知节点的 pointer 重连O(log n)：对半缩减搜索O(n)：线性扫描O(n log n)：分治加线性合并- ：双层线性循环
快速检查
快速检查
两层各跑 n 次的循环（内部 O(1)）是什么复杂度？
直接乘法则。
解答