1. 为什么要学习时间复杂度？
同一个问题，往往有不止一种算法。它们都可能得到正确答案，但运行速度可能完全不同。
例如，在一个有 100 个元素的数组中搜索数据，慢一点的算法也许感觉不明显；但当数据量增加到 100 万个时，算法之间的差距可能变成几秒、几分钟，甚至根本无法接受。
因此，评价算法不能只看“能不能得到正确结果”，还要问：
- 输入规模变大时，运行时间如何增长？
- 算法是否依赖某一台机器或某一种编译器？
- 最坏情况下，它需要执行多少工作？
时间复杂度就是用来回答这些问题的抽象工具。
本文把“计算量”限定为时间复杂度。严格来说，计算量还包括空间复杂度；空间复杂度表示算法需要多少额外内存。
2. 输入规模 n 是什么？
时间复杂度通常表示为输入规模 n 的函数。
n 不一定代表数组长度，也可以代表：
- 字符串的长度；
- 表中记录的数量；
- 图中的顶点数或边数；
- 矩阵的行数和列数；
- 要处理的文件大小。
关键在于：先明确“问题规模”是什么，再分析规模增长时算法做了多少工作。
例如，在线性表中搜索一个元素时，最自然的规模就是表中元素的数量 n。
3. 基本操作与 O(1)
为了分析算法，我们先把程序拆成一些基本操作，例如：
- 一次加法或比较；
- 一次赋值；
- 访问一个数组元素；
- 读取或修改一个指针；
- 判断一次条件。
如果某个操作的执行时间与 n 无关，就把它看作常数时间，记作：
O(1)
例如：
x = a + b;
无论数组有 10 个元素还是 100 万个元素，这条语句都只执行一次，因此是 O(1)。
注意，O(1) 表示“与输入规模无关”，并不表示实际耗时一定很小。一次复杂的库函数调用，也可能隐藏着与 n 有关的工作。
4. 大 O 记号表示什么？
如果一个算法的运行时间大致与 f(n) 成正比，就把它的时间复杂度写成：
O(f(n))
大 O 记号关注的是输入规模变大时的增长趋势，而不是某台机器上的精确秒数。
例如：
3n² + 5n + 7 = O(n²)
因为当 n 很大时，n² 项的增长速度远高于 n 和常数项。
所以分析复杂度时通常会：
- 忽略常数系数；
- 忽略低阶项；
- 保留增长最快的那一项。
常见化简规则包括：
O(2n + 10) = O(n)
O(n + n²) = O(n²)
O(5n³ + n² + 1) = O(n³)
5. 常见的时间复杂度
| 复杂度 | 常见名称 | 典型例子 |
|---|---|---|
O(1) |
常数时间 | 访问数组中的一个位置 |
O(log n) |
对数时间 | 二分搜索 |
O(n) |
线性时间 | 扫描整个数组 |
O(n log n) |
线性对数时间 | 高效的比较排序、归并排序 |
O(n²) |
平方时间 | 两层嵌套循环、简单排序 |
O(2ⁿ) |
指数时间 | 某些暴力枚举算法 |
增长速度从快到慢大致是：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
这里的“小于”表示增长得更慢，而不是实际运行时间在所有情况下都更短。常数因素、输入分布和实现细节也会影响实际表现。
6. 如何分析循环？
6.1 单层循环：O(n)
for (int i = 0; i < n; i++) {
process(a[i]);
}
循环最多执行 n 次，每次工作量为 O(1)，因此总复杂度是：
n × O(1) = O(n)
6.2 每次减半：O(log n)
while (n > 1) {
n = n / 2;
}
执行过程是：
n, n/2, n/4, n/8, ...
经过 k 次除以 2 后，规模变成 n / 2ᵏ。当它降到 1 时，有：
2ᵏ ≈ n
因此 k ≈ log₂ n，复杂度为 O(log n)。
6.3 两层嵌套循环：O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
process(i, j);
}
}
外层执行 n 次，内层每次也执行 n 次：
n × n × O(1) = O(n²)
如果内层循环的上限随 i 变化，例如：
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
process(i, j);
}
}
总执行次数是：
0 + 1 + 2 + ... + (n - 1) = n(n - 1) / 2
仍然属于 O(n²)。
6.4 顺序执行：取增长更快的一项
for (int i = 0; i < n; i++) { // O(n)
process(a[i]);
}
for (int i = 0; i < n; i++) { // O(n²)
for (int j = 0; j < n; j++) {
process(i, j);
}
}
两段程序是顺序执行，总复杂度为：
O(n) + O(n²) = O(n²)
顺序相加，最后保留增长更快的项。
7. 例子一：线性搜索
线性搜索从头到尾逐个检查元素：
int linear_search(const int a[], int n, int key) {
for (int i = 0; i < n; i++) {
if (a[i] == key) {
return i;
}
}
return -1;
}
最好情况
第一个元素就是目标，只比较一次：
O(1)
最坏情况
目标位于最后，或者根本不存在，需要检查全部 n 个元素：
O(n)
平均情况
如果目标随机出现在数组中，平均需要检查大约 n/2 个元素。去掉常数系数后，仍然是：
O(n)
因此，通常说线性搜索是 O(n) 算法。除非特别说明，算法分析通常优先讨论最坏情况。
8. 例子二：二分搜索
二分搜索要求数据已经按顺序排列。每次比较中间元素，然后把搜索范围缩小一半：
int binary_search(const int a[], int n, int key) {
int low = 0;
int high = n - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (a[middle] == key) {
return middle;
}
if (key < a[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
搜索范围的变化是：
n → n/2 → n/4 → n/8 → ...
所以最多执行 log₂ n 次比较，时间复杂度为：
O(log n)
这就是为什么二分搜索在大规模数据上通常远快于线性搜索。但它也有前提：数据必须有序，而且数据结构要支持快速访问中间位置。
9. 注册数据也需要分析
不能只分析“搜索”这一项操作。为了搜索，数据通常必须先被注册或插入结构中。
例如：
- 向数组末尾追加一个元素：通常是
O(1)； - 向有序数组中间插入一个元素：为了腾出位置，可能需要移动大量元素，是
O(n)； - 向平衡搜索树插入一个元素：通常是
O(log n)； - 使用哈希表插入：在合适条件下平均可接近
O(1)。
因此，选择数据结构时，应该同时考虑：
- 插入的频率；
- 搜索的频率；
- 删除的频率；
- 是否需要保持有序；
- 可用内存大小。
一个只在搜索时很快、但每次更新都很慢的数据结构，不一定适合所有程序。
10. 最坏情况、平均情况与最好情况
同一个算法，面对不同输入时可能需要不同的时间。
- 最好情况：输入刚好使算法最快；
- 最坏情况：输入使算法执行最多工作；
- 平均情况：对各种输入的运行成本取平均。
例如快速排序：
- 平均时间复杂度通常为
O(n log n)； - 最坏时间复杂度可能退化为
O(n²)。
平均情况有时更接近实际表现，但计算平均情况往往需要对输入分布作出假设，分析也更困难。因此，教材和工程文档如果只写“时间复杂度”，通常默认指最坏情况的渐进复杂度。
11. 时间复杂度不是实际秒数
O(n) 并不意味着程序一定比某个 O(log n) 程序更快。实际运行时间还受到以下因素影响：
- CPU 和内存的速度；
- 编译器生成的代码；
- 常数系数；
- 缓存命中率和内存访问局部性；
- 输入数据的实际规模；
- 程序语言和实现方式。
时间复杂度的价值在于提供一种与具体机器相对独立的比较方式：当 n 足够大时，增长阶数通常比常数优化更重要。
12. 时间与空间的权衡
有时可以用更多内存换取更短的运行时间。
例如，线性搜索不需要额外的索引结构，但每次搜索都可能扫描整个数组；如果预先建立哈希表或索引，搜索可以更快，但要付出额外内存和构建成本。
这就是时间—空间权衡：
减少运行时间，往往需要更多辅助空间；
节省内存，往往需要执行更多计算。
不存在对所有问题都最优的算法。真正的选择取决于数据规模、操作比例、硬件资源和程序的实际目标。
13. 一套实用的分析步骤
拿到一段程序时，可以按以下顺序分析：
- 明确输入规模
n是什么； - 找出程序中重复执行的核心操作；
- 估计每个循环执行多少次；
- 分析嵌套循环是相乘还是相加；
- 检查条件分支和提前返回；
- 分别考虑最好、平均和最坏情况；
- 忽略常数系数和低阶项；
- 检查算法是否使用了额外空间；
- 确认数据结构的插入、搜索和删除成本。
最后，把结果写成最主要的增长项，例如 O(n)、O(log n) 或 O(n²)。
14. 小结
- 时间复杂度描述的是运行时间随输入规模增长的趋势；
O(1)表示与输入规模无关的常数时间；- 单层遍历通常是
O(n)，每次减半通常是O(log n)； - 两层规模都为
n的嵌套循环通常是O(n²)； - 顺序执行的复杂度相加，最后保留增长更快的一项；
- 线性搜索是
O(n)，二分搜索是O(log n)，但二分搜索要求数据有序； - 分析算法时不能只看搜索，还要看插入、删除和预处理；
- 复杂度不是实际秒数，而是与具体机器相对独立的增长模型；
- 更快的时间复杂度有时需要更多内存，算法选择本质上是多种资源之间的权衡。