难点概览
算法设计里，“正确性”只是基础，真正比较算法优劣时，核心看 效率。效率通常用两类指标衡量：
- 时间复杂度：算法运行时间随问题规模 n 增大而变化的趋势。
- 空间复杂度：算法运行过程中额外占用存储空间随 n 增大而变化的趋势。
这里最容易混淆的是：复杂度不是精确秒数，也不是机器上实际跑了多久，而是抽象出来的“增长趋势”。
教材截图
一句话先讲清
时间复杂度看“执行次数怎么随 n 增长”，空间复杂度看“额外空间怎么随 n 增长”。分析时只保留增长最快的主导项，忽略常数、低阶项和机器差异。
为什么要引入渐近复杂度？
同一个程序在不同电脑、不同编译器、不同输入数据下，实际运行时间可能差别很大。如果直接用“跑了几秒”评价算法，就不够稳定。
所以算法分析引入 渐近复杂度分析：
- 不关心某一次运行的具体秒数；
- 关心输入规模 n 越来越大时，资源消耗的增长趋势；
- 用时间复杂度和空间复杂度抽象描述算法效率。
例如：
| 表达式 | 复杂度 | 原因 |
|---|---|---|
| T(n)=3n²+100n+5 | O(n²) | n 足够大时，n² 项增长最快 |
| T(n)=2ⁿ+n¹⁰⁰ | O(2ⁿ) | 指数级最终增长快于多项式 |
| T(n)=500 | O(1) | 执行次数不随 n 增长 |
时间复杂度：看执行次数的增长趋势
时间复杂度通常记作：
T(n)=O(f(n))
它表示：当 n 足够大时，T(n) 的增长速度不会超过 f(n) 的常数倍。
更通俗地说：
O(f(n)) 不是精确等号，而是一个“增长速度上界”的描述。
分析时间复杂度时，常用做法是：
- 找出基本运算，也就是最能代表算法耗时的关键操作；
- 计算基本运算执行次数；
- 去掉常数和低阶项；
- 保留增长最快的项。
例子：逆序查找的最好、最坏、平均时间复杂度
教材中给了一个从数组末尾向前查找 k 的例子：
int i = n - 1;
while (i >= 0 && A[i] != k) {
i--; // 基本运算
}
return i;这个算法从 A[n-1] 开始向前找 k。
| 情况 | 输入特征 | 基本运算执行次数 | 时间复杂度 |
|---|---|---|---|
| 最好情况 | A[n-1] 刚好等于 k | 0 次或常数次 | O(1) |
| 最坏情况 | k 不存在，或在最前面 | n 次左右 | O(n) |
| 平均情况 | k 出现在各位置概率近似相同 | 大约 n/2 次 | O(n) |
注意：平均情况下虽然大约是 n/2 次，但复杂度仍然是 O(n)，因为常数系数 1/2 会被忽略。
考试和教材中通常更重视 最坏时间复杂度，因为它给出了运行时间的确定性上界。
加法规则：顺序执行取最大
如果两段代码顺序执行，时间复杂度分别是 O(f(n)) 和 O(g(n))，那么总时间复杂度是：
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
例如：
a(); // O(1)
b(); // O(n)
c(); // O(n²)三段代码依次执行，总复杂度不是 O(1+n+n²) 写到最后，而是保留最高阶：
O(1)+O(n)+O(n²)=O(n²)
这就是“顺序结构看最大项”。
乘法规则：嵌套执行相乘
如果一段代码嵌套在另一段代码内部，外层执行 O(f(n)) 次，内层每次执行 O(g(n))，则总时间复杂度是：
O(f(n)) × O(g(n)) = O(f(n)g(n))
例如：
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
x++; // O(1)
}
}外层循环 n 次，内层每次循环 n 次，总执行次数约为 n×n，因此复杂度是：
O(n²)
如果再套一层 n 次循环，就会变成 O(n³)。
常见时间复杂度阶次
按增长速度从慢到快，常见复杂度大致如下：
| 阶次 | 名称 | 直观理解 |
|---|---|---|
| O(1) | 常数阶 | 与 n 无关，输入再大也差不多 |
| O(log₂n) | 对数阶 | 每次把问题规模缩小一部分，如二分查找 |
| O(n) | 线性阶 | 每个元素大致处理一次 |
| O(nlog₂n) | 线性对数阶 | 常见于高效排序，如归并排序、快速排序平均情况 |
| O(n²) | 平方阶 | 两层 n 级循环 |
| O(n³) | 立方阶 | 三层 n 级循环 |
| O(2ⁿ) | 指数阶 | 穷举子集、递归爆炸常见 |
| O(n!) | 阶乘阶 | 全排列类暴力搜索 |
一句话记忆：
常数、对数很优秀；线性还能接受；平方开始变重；指数和阶乘通常要警惕。
空间复杂度：看额外辅助空间
空间复杂度记作：
S(n)=O(g(n))
它表示算法在运行过程中所需额外存储空间随 n 增长的趋势。
程序执行时占用的空间大致包括：
- 指令、常数、变量等固定开销；
- 输入数据本身；
- 辅助空间，例如临时数组、递归调用栈、指针结构等。
分析空间复杂度时，通常只关注 额外使用的辅助空间。输入数据本身一般不算入算法额外空间。
空间复杂度例子
例 1：只使用几个变量
int sum = 0;
for (int i = 0; i < n; i++) {
sum += A[i];
}这里除了输入数组 A，只额外使用了 sum 和 i 两个变量，额外空间不随 n 增大：
空间复杂度：O(1)
例 2：新建一个长度为 n 的数组
int B[n];
for (int i = 0; i < n; i++) {
B[i] = A[i];
}这里额外创建了一个长度为 n 的辅助数组 B：
空间复杂度：O(n)
例 3：递归调用栈
int f(int n) {
if (n == 0) return 1;
return n * f(n - 1);
}递归深度为 n，需要 n 层调用栈：
空间复杂度：O(n)
时间复杂度 vs 空间复杂度
| 对比项 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 衡量对象 | 执行时间增长趋势 | 额外存储空间增长趋势 |
| 常用记号 | T(n)=O(f(n)) | S(n)=O(g(n)) |
| 常见来源 | 循环、递归、基本运算次数 | 临时数组、递归栈、辅助表 |
| 分析重点 | 最高阶增长项 | 额外辅助空间 |
| 典型问题 | “这段代码跑多少次？” | “这段代码额外占多少内存？” |
常见误区
误区 1：把实际运行时间等同于时间复杂度
实际运行时间受硬件、语言、编译器和数据状态影响；时间复杂度关注的是随 n 增长的趋势。
误区 2：保留常数系数
O(3n)、O(n/2)、O(100n) 都可以简化为 O(n)。复杂度分析不关心常数倍差异。
误区 3：顺序代码把复杂度相加后不化简
O(n)+O(n²) 应化简为 O(n²)，因为 n² 增长更快。
误区 4：嵌套循环一定是 O(n²)
不一定。要看每层循环的次数。如果外层 n 次，内层 log₂n 次，则是 O(nlog₂n)。
误区 5：空间复杂度把输入数组也算进去
通常分析的是额外辅助空间。输入数据是问题本身，不作为算法额外空间计算。
考试怎么问？
常见考法包括：
- 给一段循环代码，求时间复杂度；
- 给递归式或递归代码，判断时间/空间复杂度；
- 判断最好、最坏、平均复杂度；
- 区分顺序执行和嵌套执行，用加法规则或乘法规则；
- 判断算法是否创建了 O(n) 辅助空间。
做题时可以按这个步骤：
先找基本运算 → 再数执行次数 → 判断顺序还是嵌套 → 保留最高阶 → 最后写 O 记号。
自测题
题 1
for (int i = 0; i < n; i++) {
x++;
}
for (int j = 0; j < n * n; j++) {
y++;
}这段代码的时间复杂度是多少？
第一段是 O(n)，第二段是 O(n²)，顺序执行取最大，因此总时间复杂度是 O(n²)。
题 2
int B[n];
for (int i = 0; i < n; i++) {
B[i] = A[i];
}这段代码的空间复杂度是多少？
额外创建了长度为 n 的数组 B，因此空间复杂度是 O(n)。
最后总结
时间复杂度：看算法运行次数随 n 的增长趋势。
空间复杂度：看算法额外辅助空间随 n 的增长趋势。
顺序执行用加法规则取最大，嵌套执行用乘法规则相乘。
大 O 分析只保留主导增长项，忽略常数和低阶项。