在学习链表、排序和搜索之前，需要先有一把比较算法的尺子。复杂度不是给代码贴一个神秘公式，而是描述：输入规模变大时，工作量怎样增长。
为什么不能只看运行秒数
同一段程序的耗时会受到 CPU、编译器、优化级别、系统负载和测试数据影响。秒数适合做最终测量，却不适合作为第一层通用分析。
复杂度忽略机器常数，关注增长趋势。例如处理 n 个元素：
- 做固定几步：
O(1)； - 每个元素看一次：
O(n)； - 每对元素都比较：
O(n²)； - 每次把范围减半：
O(log n)。
输入规模必须先定义
n 不一定是数组长度。对图算法，常同时使用：
V：顶点数；E：边数。
对字符串算法，可能使用字符串长度 m。不说明规模含义，O(n) 就没有完整意义。
从循环数操作
for (size_t i = 0; i < n; i++) {
sum += data[i];
}
循环执行约 n 次，每次工作量近似固定，因此是 O(n)。
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
count++;
}
}
内层对每个 i 都执行 n 次，总计 n × n，所以是 O(n²)。
两个先后执行的循环是相加而不是相乘：
O(n) + O(n) = O(2n) = O(n)
Big O 关注最高阶增长，所以省略常数和低阶项：
3n² + 5n + 100 记作 O(n²)
这并不表示常数永远不重要。两个同为 O(n) 的算法，在真实机器上仍可能差很多；复杂度只是第一层筛选。
对半缩小为什么是对数
二分查找每次把候选范围减半：
n -> n/2 -> n/4 -> ... -> 1
问“除以 2 多少次会到 1”，答案约是 log₂ n。一百万个元素约二十次就能缩到一个位置。
最好、平均和最坏情况
顺序查找可能第一项就命中，也可能检查完整个数组：
- 最好：
O(1)； - 最坏：
O(n)； - 平均：取决于输入分布和目标出现概率，不能凭感觉声称。
工程接口通常更关注最坏上界或明确的均摊保证，因为它们更容易约束延迟。
均摊复杂度
动态数组扩容时，偶尔需要申请更大的空间并复制所有元素，单次扩容可能是 O(n)。但如果容量按倍数增长，许多次尾部追加的平均成本仍可达到均摊 O(1)。
“均摊”不是“在随机输入上的平均”，而是把一串操作的总成本分摊到每次操作。
空间复杂度
空间复杂度描述额外需要多少存储。
void reverse(int *data, size_t n) {
for (size_t left = 0, right = n; left < right; ) {
--right;
int tmp = data[left];
data[left] = data[right];
data[right] = tmp;
++left;
}
}
无论 n 多大，只额外使用几个变量，所以额外空间是 O(1)。
递归还要计算调用栈。一个深度为 n 的递归，即使没有显式数组，也可能占用 O(n) 栈空间。
常见增长速度
| 复杂度 | 直觉 | 常见例子 |
|---|---|---|
O(1) | 与规模无关 | 数组按下标访问 |
O(log n) | 每次砍掉固定比例 | 二分查找 |
O(n) | 每项处理一次 | 遍历数组 |
O(n log n) | 多层分治，每层处理全部数据 | 高效比较排序 |
O(n²) | 两两组合或双重全范围循环 | 简单排序 |
O(2^n) | 每个元素取或不取 | 枚举子集 |
O(n!) | 枚举所有排列 | 全排列 |
指数和阶乘增长非常快。n=50 对 O(n²) 很小，对 O(2^n) 已经不可接受。
数据结构操作要写清前提
“链表插入是 O(1)”只有在已经持有插入位置的节点指针时成立。如果还要先从头查找位置，总操作仍是 O(n)。
“哈希表查找是 O(1)”通常指良好散列和负载控制下的平均或期望情况，最坏情况可能更差。
复杂度结论必须连同前提一起记忆。
怎样分析一段新代码
- 定义输入规模；
- 找出会随规模重复的核心操作；
- 顺序部分相加，嵌套部分相乘；
- 递归写出子问题数量、规模和每层工作；
- 只保留主导增长项；
- 单独计算额外内存和递归深度；
- 写清最好、最坏、均摊等适用条件。
后面的每个数据结构都会把“操作步骤”和“复杂度前提”放在一起解释，而不是只要求背表格。