一起动脑筋 · 先看一个小故事
机器人给三种工作量贴标签：只看第一张、看所有卡片、比较所有配对。
把过程摊开来看
- O(1)次数不随 n 增长
- O(n)随 n 线性增长
- O(n²)可能按平方增长
大 O 常用来描述增长的上界，入门时用它比较主要工作量。
O(1) 不等于只做一次；固定做十次也不随 n 增长。O(n) 也不保证精确做 n 次。
01O(1) 是什么意思？
int x = a[5];只要下标合法，普通数组按下标访问所需的基本工作不会因为数组更长而增加，因此常记作 O(1)。
02O(n) 是什么意思？
for (int i = 0; i < n; i++) {
sum += a[i];
}n 增大一倍，循环工作量大约也增大一倍，因此是线性级别 O(n)。
03O(n²) 是什么意思？
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
work();
}
}两层都执行 n 次，总工作量大约是 n × n，因此为 O(n²)。
04增长速度差多少？
| n | O(1) | O(n) | O(n²) |
|---|---|---|---|
| 10 | 常数量级 | 10 | 100 |
| 1000 | 常数量级 | 1000 | 1,000,000 |
| 100000 | 常数量级 | 100000 | 10,000,000,000 |
05两层循环一定是 O(n²) 吗？
不一定。
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
work();
}
}内层固定 10 次，总工作量是 10n，渐近仍是 O(n)。
06O(1) 一定比 O(n) 快吗？
当 n 足够大时，O(1) 的增长趋势更有优势。
但实际小数据中，常数开销也可能影响速度，因此复杂度不是实际秒数的全部。
你已经知道了什么
- O(1) 表示工作量不随 n 增长。
- O(n) 表示近似线性增长。
- O(n²) 表示近似平方增长。
- 不能简单通过循环层数判断复杂度。
- 复杂度描述增长趋势，不等于实际运行时间。
下一篇：为什么二分查找是 O(log n)？
轮到你来试一试
固定执行 20 次打印，与执行 n 次打印，增长趋势一样吗？
想好了吗？点开看解释
不一样。前者相对 n 是常数级，后者随 n 线性增长。