第8章 时间和空间效率分析

---

🎯 本章学习目标

通过本章的学习，你将能够：

1. 掌握大O表示法：理解渐近上界概念，会忽略常数和低阶项
2. 分析循环复杂度：能数清嵌套循环的执行次数，判断常见循环形态
3. 分析递归复杂度：会用递归树法推导递归算法的时间和空间复杂度
4. 区分三种情况：理解最好、最坏、平均时间复杂度的区别
5. 掌握空间复杂度：能区分输入空间、辅助空间和递归栈空间
6. 估算1秒数据量：能根据数据范围反推可接受的算法复杂度
7. 熟记常见算法复杂度：排序、查找、图遍历、DP等的时间和空间
8. 识别复杂度陷阱：避开两层循环必O(n²)、剪枝改变上界等常见误区
9. 对比算法优劣：能从时间和空间两个维度比较不同算法
10. 应对真题题型：能解决选择、判断、程序阅读等各类复杂度题目

---

🗺️ 本章知识图谱

时间和空间效率分析
├── 大O表示法基础
│   ├── 定义：渐近上界，只看增长趋势
│   ├── 三条规则：忽略常数、保留最高阶、对数底数无关
│   └── 基本法则：串行取最大、嵌套做乘法、分支看最坏
├── 时间复杂度分析
│   ├── 循环计数法
│   │   ├── 一层循环：O(n)
│   │   ├── 两层等循环：O(n²)
│   │   ├── 内层折半：O(log n)
│   │   └── 外层翻倍内层跟i走：O(n)（陷阱！）
│   ├── 递归分析法
│   │   ├── 递归式 T(n)
│   │   ├── 递归树：层数 × 每层工作量
│   │   └── 主定理思想入门
│   └── 三种情况
│       ├── 最好情况
│       ├── 平均情况
│       └── 最坏情况（考试重点）
├── 空间复杂度
│   ├── 输入空间 vs 辅助空间
│   ├── 递归栈空间 = 递归深度
│   ├── 常见算法空间对比
│   └── DP空间优化（滚动数组）
├── 量级与估算
│   ├── 量级排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
│   └── 1秒数据量经验表（C++约10⁸次操作）
├── 常见算法复杂度表
│   ├── 排序算法
│   ├── 查找算法
│   ├── 树与图遍历
│   ├── 搜索算法（指数级）
│   └── 动态规划
└── 避坑清单
    ├── 两层循环≠O(n²)
    ├── 递归空间≠节点数（看深度）
    ├── 快排最坏O(n²)
    ├── 归并空间O(n)
    ├── 图邻接表O(V+E)
    └── 剪枝不改变最坏上界

---

一、开篇 · 算法的"度量衡"

如果说前面几章我们学的是"怎么把算法写出来"，那本章要解决的就是——"这个算法够不够快、够不够省"。

复杂度分析是 GESP 八级选择题的"常驻嘉宾"：看一段代码判复杂度、给一个数据范围反推可接受的算法、比较两个算法谁更快……这类题不需要写代码，却最能检验一个选手的算法功底。

🔥 高频考点：八级试卷中，复杂度相关题目几乎每场必出 1~2 道，且常与排序、DP、图论结合考查。属于"掌握套路就稳拿分"的高性价比模块。

---

二、大O表示法基础

大O表示法描述算法运行时间（或占用空间）随输入规模 n 增长的渐近上界。它只关心增长趋势，因此：

• 忽略常数系数：3n → O(n)，5n² → O(n²)
• 只保留最高阶项：n² + 10n + 100 → O(n²)
• 对数底数无关：log₂n、log₁₀n 只差常数倍，统一写 O(log n)

分析时有三条基本法则：

法则	说明	例子
顺序结构	各段复杂度相加，取最高阶	O(n) + O(n²) = O(n²)
循环结构	循环体复杂度 × 循环次数	循环 n 次、体 O(1) → O(n)
分支结构	取所有分支中的最大复杂度	两支分别 O(n)、O(n²) → O(n²)

💡 一句话记忆：串行取最大，嵌套做乘法，分支看最坏。

---

三、时间复杂度分析的两大"套路"

套路一：数基本语句——盯住最内层循环

方法：找出执行最频繁的基本语句，数它被执行的总次数。循环次数均匀就相乘，不均匀就求和。

// C++11：外层 n 次，内层每次折半
long long cnt = 0;
for (int i = 0; i < n; ++i) {        // 外层 n 次
    for (int j = 1; j < n; j *= 2) { // 内层 log₂n 次
        ++cnt;                        // 基本语句
    }
}
// 总次数 = n × log₂n → O(n log n)

常见循环形态速查：

循环形态	总执行次数	复杂度
一层循环 i: 0→n-1	n	O(n)
两层循环各 n 次	n²	O(n²)
内层 j: 0→i-1	0+1+…+(n-1) = n(n-1)/2	O(n²)
内层 j *= 2（折半）	log₂n	O(log n)
外层 i *= 2，内层跑 i 次	1+2+4+…+n ≈ 2n	O(n)

⚠️ 易错点："两层循环 ≠ O(n²)"！务必数内层循环的实际次数。最后一行就是经典陷阱——外层翻倍、内层跟着 i 走，等比数列求和结果是 O(n)，而不是想当然的 O(n log n)。

套路二：递归式——递归树与主定理思想入门

分析递归算法，先写出递归式 T(n)（规模 n 的问题的耗时），再求解：

递归式	典型算法	复杂度
T(n) = T(n-1) + O(1)	线性递归求和	O(n)
T(n) = T(n/2) + O(1)	二分查找	O(log n)
T(n) = 2T(n/2) + O(n)	归并排序	O(n log n)
T(n) = 2T(n-1) + O(1)	斐波那契朴素递归	O(2ⁿ)

递归树分析法（八级要求掌握的核心思想）：把递归调用画成一棵树，总工作量 = 层数 × 每层所有节点的工作量之和。

• 归并排序：每层把数组对半分，树共 log₂n 层；每层所有合并操作加起来恰好处理 n 个元素 → O(n) × O(log n) = O(n log n)。
• 斐波那契递归：树高约 n，而节点数每层翻倍，总数约 2ⁿ → O(2ⁿ)。

主定理思想入门：对 T(n) = aT(n/b) + f(n)（分成 a 个规模 n/b 的子问题，划分/合并代价 f(n)），直觉上比较"叶子层代价 n^(log_b a)"与"f(n)"谁大，谁大决定总复杂度；同阶则乘个 log n。八级不要求背公式，会用递归树"层数 × 每层工作量"推导即可。

以归并排序 T(n) = 2T(n/2) + O(n) 完整走一遍递归树：第 0 层 1 个节点、处理 n 个元素；第 1 层 2 个节点、各处理 n/2 个，合计 n；第 2 层 4 个节点、各处理 n/4 个，合计还是 n……每一层的总工作量恒为 O(n)，而 n 对半切到 1 共需 log₂n 层，于是 T(n) = O(n) × O(log n) = O(n log n)。二分查找 T(n) = T(n/2) + O(1) 同理：共 log₂n 层、每层只做 O(1) 次比较，故 O(log n)。掌握这套"画树、数层、算每层总和"的流程，考试中遇到任何陌生递归代码都能现场推导。

⚠️ 易错点：时间看节点总数，空间看树的深度。斐波那契递归时间 O(2ⁿ)，但任意时刻只有一条根到叶子的调用链在栈上，递归栈深度只有 n，故空间是 O(n)——两者千万不要混为一谈。

最好 / 最坏 / 平均情况

同一个算法，输入不同，表现可能不同：

算法	最好	平均	最坏
顺序查找	O(1)（第一个就是）	O(n)（等概率均摊 n/2 次）	O(n)
冒泡排序（带提前退出）	O(n)（已有序）	O(n²)	O(n²)
插入排序	O(n)（已有序）	O(n²)	O(n²)
快速排序	O(n log n)	O(n log n)	O(n²)（数组已有序且基准选端点）

🔥 高频考点：快速排序的最坏情况 O(n²) 是八级选择题的"老面孔"。触发条件是每次划分都极不平衡（如已有序数组 + 固定取首元素为基准）；随机化选基准或三数取中可在实际中规避。注意：归并排序、堆排序三种情况都是 O(n log n)，没有"最坏退化"。

---

四、空间复杂度：别只盯着时间

3.1 输入空间 vs 辅助空间

• 输入空间：存放输入数据本身（如长度 n 的数组占 O(n)），通常不计入算法的"额外开销"。
• 辅助空间（额外空间）：算法运行中额外开辟的空间（临时数组、哈希表、DP 表等）。
• 递归栈空间：递归调用时系统栈中保存的参数、局部变量、返回地址。

题目说"空间复杂度"时，一般指辅助空间 + 递归栈的总和。为什么要强调"额外"二字？因为排序题里，输入数组那 O(n) 是题目本身给的，任何算法都省不掉；能体现算法设计水平的，是你另外开了多少空间。比如原地排序（冒泡、快排、堆排）的额外空间是 O(1) 或 O(log n)，而归并排序必须再开一块 O(n) 的临时数组——同样 O(n log n) 的时间，空间占用立分高下。

另一个高频陷阱是递归栈：很多同学分析递归函数时只数了数组变量，忘了"调用本身也占地方"。每次函数调用，系统都会在栈上压入一帧（参数、返回地址、局部变量），递归多深，栈里就同时压着多少帧。这也是为什么深度为 n 的朴素递归在 n 很大（如 n=10⁶）时会栈溢出（Stack Overflow）——不是算法错了，是栈空间扛不住了。

3.2 递归栈空间怎么算

递归栈空间 = 递归深度 × 每层栈帧大小（每层局部变量为常数时即 O(深度)）。

• 线性递归（每次 n→n-1）：深度 n → O(n)，如斐波那契递归、链状图上的 DFS。
• 折半递归（每次 n→n/2）：深度 log n → O(log n)，如归并排序、快速排序（平均）。

常见算法空间复杂度一览：

算法	辅助空间	递归栈	总空间
冒泡 / 选择 / 插入 / 堆排序	O(1)	—	O(1)
快速排序	O(1)	O(log n) 平均 / O(n) 最坏	O(log n)
归并排序	O(n)（合并临时数组）	O(log n)	O(n)
计数排序	O(k)（值域大小）	—	O(k)
斐波那契朴素递归	O(1)	O(n)	O(n)
0/1 背包（二维 DP 表）	O(nV)	—	O(nV)
0/1 背包（滚动数组）	O(V)	—	O(V)

⚠️ 易错点：归并排序的时间是 O(n log n)，但空间是 O(n)（合并用的临时数组），它不是原地排序；而堆排序时间 O(n log n)、空间 O(1)，是原地排序。时间和空间要分开记。

动态规划的空间优化是八级常考的"省钱"技巧。以 0/1 背包为例：

// C++11：0/1 背包滚动数组——时间 O(nV)，空间 O(V)
int knapsack(int n, int V, vector<int>& w, vector<int>& v) {
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < n; ++i)
        for (int j = V; j >= w[i]; --j)   // 必须倒序：保证每件物品只选一次
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[V];
}

二维 DP 表 O(nV) 里，第 i 行只依赖第 i-1 行，于是可以压成一维 O(V)——时间不变，空间少一维。这正是第9章《算法优化》的内容。

---

五、常见复杂度量级与"1秒数据量"估算

4.1 量级排序（⭐ 必背）

增长率从慢到快：

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

直观感受一下（n=100 时的大致操作数）：log n ≈ 7；n = 100；n log n ≈ 700；n² = 1 万；n³ = 100 万；2ⁿ ≈ 1.27×10³⁰（天文数字）。

4.2 "1秒能处理多大数据量"经验表 🔥

经验前提：C++ 每秒约能执行 10⁸ 次简单操作。据此反推 n 的安全上限：

复杂度	C++（1秒）安全上限
O(log n)	n 可达 10¹⁸
O(√n)	n 可达 10¹⁶
O(n)	约 10⁷ ~ 10⁸
O(n log n)	约 10⁶ ~ 2×10⁶
O(n²)	约 5000 ~ 10⁴
O(n³)	约 200 ~ 300
O(2ⁿ)	n ≤ 20 ~ 25
O(n!)	n ≤ 10 ~ 12

估算口诀：拿到题先看 n 的范围——n≤10 想指数/阶乘搜索，n≤25 想 2ⁿ 或 meet-in-the-middle，n≤500 想 O(n³)，n≤5000 想 O(n²)，n≤10⁶ 想 O(n log n)，n≤10⁷ 只能 O(n)，n 到 10¹⁸ 必须 O(log n)。

⚠️ 易错点：经验值假设循环体是"简单语句"。若循环体内还藏着排序 O(n log n)、vector 拷贝等，要把内在复杂度乘上去。例如双层循环里每层调用一次排序，总复杂度是 O(n² · n log n) = O(n³ log n)，而不是 O(n²)。

---

六、各类算法复杂度对照表（⭐ 核心表）

5.1 排序算法

排序算法	最好	平均	最坏	额外空间	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶 / 基数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定

（n 为元素个数，k 为值域/桶数）

🔥 高频考点：①冒泡、插入的最好情况 O(n) 必须以"已有序时提前结束"为前提，裸写两层循环仍是 O(n²)；②三个 O(n log n) 排序中，只有归并最坏也是 O(n log n) 且稳定，但代价是 O(n) 空间；③计数/桶排序是"非比较排序"，靠空间换时间，O(n+k) 成立的前提是值域 k 不能太大。

5.2 查找算法

查找算法	前提	时间复杂度
顺序查找	无	O(n)（最好 O(1)，平均 n/2）
二分查找	序列有序	O(log n)

// C++11：二分查找，区间每次折半 → O(log n)
int binarySearch(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;   // 防溢出写法
        if (a[mid] == x) return mid;
        else if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

区间长度 n → n/2 → n/4 → … → 1，折半 log₂n 次后结束，这就是 O(log n) 的来源。二分查找依赖随机访问，故作用于链表上时退化为 O(n)。

5.3 树与图的遍历

算法	时间复杂度	空间复杂度
二叉树前/中/后/层序遍历	O(n)（n 个节点各访问常数次）	O(h)，h 为树高（平衡时 O(log n)）
二叉搜索树查找	平均 O(log n)，最坏 O(n)（退化成链）	O(1) / O(h)
图的 DFS / BFS（邻接表）	O(V+E)	O(V)（访问标记 + 栈/队列）
图的 DFS / BFS（邻接矩阵）	O(V²)	O(V)

⚠️ 易错点：邻接表中图遍历是 O(V+E)（每个顶点访问一次、每条边检查一次），不是 O(V·E)；邻接矩阵找邻接点要扫整行，才是 O(V²)。V 是顶点数、E 是边数，两个维度都要出现在答案里。

5.4 搜索算法：指数级状态空间

DFS/BFS 本身只是"遍历框架"，其复杂度由状态空间大小决定：

• 子集型搜索（每个元素选或不选）：状态数 2ⁿ → O(2ⁿ)，如子集枚举、0/1 背包暴力版。
• 排列型搜索（n 个元素的全排列）：状态数 n! → O(n!)，如八皇后（实际约 n! 量级）、全排列问题。
• 网格/棋盘型：状态数取决于格子数与分支因子，通常也是指数级。

🔥 剪枝、记忆化可以让实际运行大大加快，但不改变最坏情况的复杂度上界——考试问"最坏情况复杂度"时，搜索题大胆选指数级。如何科学剪枝与优化，正是第9章《算法优化》的主题。

5.5 分治与动态规划

DP 复杂度分析套路：时间 = 状态数 × 每个状态的转移代价；空间 = 状态数（× 每状态存储）。写 DP 时先明确"状态是几维的"（决定状态数），再数"每个状态枚举多少种决策"（决定转移代价），两者一乘就是答案。例如 0/1 背包：状态是"前 i 件物品、容量 j"共 n×(V+1) 个，每个状态只有"选/不选"两种 O(1) 决策，故时间 O(nV)；区间 DP 有 O(n²) 个区间状态，每个区间要枚举 O(n) 个分割点，故 O(n³)。这套思路对所有 DP 题通用，比逐个背结论可靠得多。

经典对照——斐波那契数列：

// C++11
// 写法①：朴素递归——时间 O(2ⁿ)，空间 O(n)
long long fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

// 写法②：递推——时间 O(n)，空间 O(1)
long long fib2(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

同一个问题，朴素递归把大量子问题重复计算（递归树节点约 2ⁿ 个），递推则每个状态只算一次——O(2ⁿ) 到 O(n) 的天壤之别，这就是"重叠子问题"的威力。

常见 DP 复杂度速查：

DP 模型	状态数	每状态转移	时间	空间
斐波那契递推	n	O(1)	O(n)	O(1) 滚动后
0/1 背包	n×(V+1)	O(1)	O(nV)	O(nV) → O(V)
最长公共子序列 LCS	n×m	O(1)	O(nm)	O(nm) → O(min(n,m))
最长上升子序列 LIS	n	O(n) / O(log n)	O(n²) / O(n log n)	O(n)
区间 DP（石子合并）	O(n²) 个区间	O(n) 枚举分割点	O(n³)	O(n²)

5.6 复杂度分析"避坑清单"

最后汇总八级阅卷中最常见的六类失分点，考前过一遍：

#	典型错误想法	正确结论
1	"两层嵌套循环一定是 O(n²)"	看内层实际次数：j *= 2 型内层是 O(log n)；外层翻倍、内层跟 i 走可低至 O(n)
2	"递归算法空间等于递归树节点数"	时间看节点总数，空间只看树深（同一时刻栈上只有一条调用链）
3	"快速排序任何情况都是 O(n log n)"	最坏 O(n²)；归并、堆排序才是三者皆 O(n log n)
4	"归并排序空间 O(log n)"	递归栈 O(log n)，但合并临时数组 O(n)，总空间 O(n)
5	"图遍历是 O(V·E)"	邻接表为 O(V+E)（每个顶点、每条边各处理一次）；O(V²) 是邻接矩阵
6	"加了剪枝复杂度就变低了"	剪枝只改善实际运行，不改变最坏上界；问最坏情况仍按状态空间总数作答

---

---

七、📝 实战练习

练习题 1（单选题）

题目： 用大 O 表示法描述算法时间复杂度 T(n) = 5n² + 3n + 2，正确的是（ ）

A. O(5n²)
B. O(n²)
C. O(5n² + 3n)
D. O(5n² + 3n + 2)

🔑 点击查看答案与解析

答案： B **解析：**大O表示法忽略常数系数（去掉5）、只保留最高阶项（去掉低阶的3n和常数2），因此为 O(n²)。大O描述的是增长趋势，不关心具体系数。

练习题 2（单选题）

题目： 下列代码的时间复杂度是（ ）

int fun(int n) {
    int count = 0;
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < i; j++) {
            count++;
        }
    }
    return count;
}

A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)

🔑 点击查看答案与解析

答案： A **解析：**外层 i 依次取 1, 2, 4, …, n，共 log₂n 轮；内层循环执行 i 次。总次数 = 1+2+4+…+n = 2n-1（等比数列求和）→ O(n)。 ⚠️ 这是经典陷阱题：两层循环不一定是 O(n²)，也不一定是 O(n log n)，务必老老实实数次数。

练习题 3（单选题）

题目： 某题数据规模 n = 2×10⁵，假设 C++ 每秒约执行 10⁸ 次简单操作，下列哪种复杂度的算法最稳妥地能在 1 秒内通过？（ ）

A. O(n²)
B. O(n√n)
C. O(n log n)
D. O(2ⁿ)

🔑 点击查看答案与解析

答案： C **解析：**n² = 4×10¹⁰，远超 10⁸，A 错；2ⁿ 是天文数字，D 错；n√n ≈ 2×10⁵×447 ≈ 9×10⁷，简单语句勉强卡线但循环体稍复杂就超时，不稳妥；n log n ≈ 2×10⁵×18 ≈ 3.6×10⁶，游刃有余。 💡 估算题先算操作数量级，再对照"1秒经验表"，留足余量更稳妥。

练习题 4（单选题）

题目： 下列排序算法中，最坏情况下时间复杂度仍然为 O(n log n) 的是（ ）

A. 快速排序
B. 归并排序
C. 冒泡排序
D. 插入排序

🔑 点击查看答案与解析

答案： B 解析：快排最坏退化为 O(n²)（有序数组 + 端点基准）；冒泡、插入最坏 O(n²)；只有归并排序最好/平均/最坏均为 O(n log n)。堆排序同样三者皆 O(n log n)，可一并记忆。

练习题 5（判断题）

题目： 斐波那契数列的朴素递归算法，时间复杂度和空间复杂度都是 O(2ⁿ)。（ ）

🔑 点击查看答案与解析

答案： 错误 ❌ **解析：**时间复杂度是 O(2ⁿ)（递归树节点总数指数级增长），但空间复杂度是 O(n)——任意时刻栈上只有一条深度为 n 的调用链，递归栈空间只看树的深度，不看节点总数。时间看节点总数，空间看树的深度，两者不要混为一谈。

练习题 6（判断题）

题目： 对搜索算法加上剪枝优化后，其最坏情况的时间复杂度会降低。（ ）

🔑 点击查看答案与解析

答案： 错误 ❌ **解析：**剪枝只能改善实际运行时间，不改变最坏情况的复杂度上界。考试问"最坏情况复杂度"时，搜索题仍按状态空间总数（如 2ⁿ 或 n!）作答。剪枝是"实战优化"，不是"理论改进"。

练习题 7（程序阅读题）

题目： 阅读以下递归函数，回答问题。

int fun(int n) {
    if (n <= 1) return 1;
    return fun(n / 2) + fun(n / 2);
}

（1）该函数的时间复杂度是？
A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)

（2）该函数的空间复杂度是？
A. O(n)
B. O(log n)
C. O(n²)
D. O(1)

🔑 点击查看答案与解析

答案： （1）A　（2）B

解析：

• 时间复杂度：O(n)

  递归式：T(n) = 2T(n/2) + O(1)

  画递归树分析：

  • 第 0 层：1 个节点，每个 O(1)，总 O(1)
  • 第 1 层：2 个节点，总 O(1)
  • 第 2 层：4 个节点，总 O(1)
  • ……
  • 第 log n 层：n 个节点（叶子），总 O(n)

  总节点数 = 1 + 2 + 4 + ... + n = 2n - 1 = O(n)

  注意：这和归并排序不同！归并排序每层有 O(n) 的合并操作，而这里每层每个节点只有 O(1) 的加法（除了递归调用本身）。

• 空间复杂度：O(log n)

  递归深度为 log₂n，每层栈帧常数大小，故空间 O(log n)。

练习题 8（简答题）

题目： 关于图的遍历，回答下列问题：

（1）用邻接表存储的无向图，DFS 深度优先遍历的时间复杂度和空间复杂度分别是多少？请简述理由。

（2）如果改用邻接矩阵存储该图，DFS 遍历的时间复杂度变为多少？为什么？

（3）有人说"图遍历的时间复杂度是 O(V·E)"，这种说法对吗？请解释原因。

🔑 点击查看答案与解析

解析：

1. 时间 O(V+E)，空间 O(V)。每个顶点访问一次 O(V)，每条边在邻接表中被检查一次 O(E)；访问标记数组与递归栈/队列共 O(V)。
2. 邻接矩阵存储时，找每个顶点的邻接点要扫一整行（V个元素），总时间变为 O(V²)。
3. O(V·E) 的错误在于把"顶点数"和"边数"相乘了。实际上，邻接表中所有顶点的邻接表长度之和恰好等于 2E（无向图），所以遍历所有边的总开销是 O(E)，加上访问顶点的 O(V)，就是 O(V+E)。V 和 E 是相加关系，不是相乘关系——这就像"数全班所有同学的头发总数"，是把每个人的头发数加起来，而不是"人数 × 某人的头发数"。

---

练习题 9（单选题）

题目： 关于均摊复杂度（Amortized Analysis），下列说法正确的是？

A. 均摊复杂度就是平均复杂度，两者是同一个概念
B. 动态数组 vector 的 push_back 操作最坏 O(n)，但均摊复杂度是 O(1)
C. 均摊复杂度分析后，最坏情况的复杂度就变低了
D. 均摊复杂度只适用于数组，不适用于其他数据结构

🔑 点击查看答案与解析

答案： B

解析：

• A 错误：均摊复杂度 ≠ 平均复杂度。平均复杂度是对输入概率求期望；均摊复杂度是对"一系列操作总代价 ÷ 操作次数"求平均，不涉及概率假设
• B 正确 ✅：vector 的 push_back 大部分时候是 O(1)，只有在数组满了需要扩容时才是 O(n)（要复制所有元素）。但因为每次扩容后数组大小翻倍，n 次操作总代价是 O(n)，所以均摊下来每次 O(1)
• C 错误：均摊分析不改变最坏情况的单次复杂度，只是说明"长期来看平均每次很便宜"。单次最坏仍是 O(n)
• D 错误：均摊分析适用于很多数据结构，如二项堆、斐波那契堆、并查集等

💡 经典例子：往空 vector 里 push_back n 个元素，总拷贝次数 = n + n/2 + n/4 + ... ≈ 2n，均摊每次 2 次拷贝 → 均摊 O(1)。

---

练习题 10（编程题）

题目： 题目描述：用滚动数组优化 0/1 背包的空间。给定 n 件物品，每件物品有重量 w[i] 和价值 v[i]，背包容量为 V。求背包能装的最大价值。

要求：空间复杂度 O(V)（使用一维滚动数组），不能用二维数组。

输入：第一行两个整数 n, V；第二行 n 个整数 w[i]；第三行 n 个整数 v[i]
输出：一个整数，最大价值

样例输入：

3 5
2 3 4
3 4 5

样例输出：

7

🔑 点击查看答案与解析

答案： 参考代码（滚动数组优化）：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXV = 1005;
int dp[MAXV];  // 一维数组，空间 O(V)
int w[105], v[105];

int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 0; i < n; i++) cin >> w[i];
    for (int i = 0; i < n; i++) cin >> v[i];
    
    // dp[j] 表示容量为 j 的背包能装的最大价值
    for (int i = 0; i < n; i++) {           // 枚举物品
        for (int j = V; j >= w[i]; j--) {   // 必须倒序枚举容量！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    cout << dp[V] << endl;
    return 0;
}

解析：0/1 背包空间优化原理：

• 二维 DP：dp[i][j] 表示前 i 件物品、容量 j 的最大价值 → 空间 O(nV)
• 观察发现：第 i 行只依赖第 i-1 行的数据 → 可以压成一维 → 空间 O(V)

为什么要倒序枚举 j？

因为 0/1 背包每件物品只能选一次。如果正序枚举 j：

• dp[j - w[i]] 可能已经被"第 i 件物品"更新过了
• 这意味着第 i 件物品可能被使用了多次 → 变成了"完全背包"

倒序枚举保证 dp[j - w[i]] 存的还是"第 i-1 件物品"的状态，每件物品只使用一次。

样例验证（n=3, V=5）：

• 物品1：w=2, v=3 → 装，价值3
• 物品2：w=3, v=4 → 装物品1+2 = 3+4 = 7（重量5，满了）
• 物品3：w=4, v=5 → 装不下，或者装物品1+3=3+5=8但重量6>5不行，装物品3价值5 < 7
• 最大价值 = 7 ✓

🔥 八级高频考点：0/1 背包滚动数组优化是空间复杂度分析的经典案例——时间不变 O(nV)，空间从 O(nV) 降到 O(V)。记住口诀：01 背包倒着推，完全背包顺着推。

---

八、📊 考点总结表

考点	重要程度	出题形式	易错点
大O表示法规则	⭐⭐⭐	选择、判断	忘记忽略常数系数、保留低阶项
循环复杂度分析	⭐⭐⭐	选择、程序阅读	两层循环想当然O(n²)，不数内层实际次数
递归复杂度（递归树）	⭐⭐⭐	选择、判断	时间和空间混淆，空间看深度不是节点数
最好/最坏/平均情况	⭐⭐	选择、判断	快排最坏O(n²)常记错；归并三者都是O(n log n)
空间复杂度（含递归栈）	⭐⭐⭐	选择、判断	漏掉递归栈；归并空间O(n)而非O(log n)
1秒数据量估算	⭐⭐⭐	选择	估算时不留余量；n√n等中间量级判断不准
排序算法复杂度对比	⭐⭐⭐	选择、判断	稳定性、空间、最坏情况三者张冠李戴
图遍历复杂度（邻接表vs矩阵）	⭐⭐	选择	误写为O(V·E)；混淆邻接表和邻接矩阵
DP复杂度分析	⭐⭐	选择	时间=状态数×转移代价，常漏乘转移代价
剪枝与复杂度上界	⭐⭐	判断	以为剪枝改变最坏复杂度上界

---

⭐ 必背速记卡

┌─────────────────────────────────────────┐
│  1. 大O三规则：忽略常数、留最高阶、      │
│     对数底数无关                        │
├─────────────────────────────────────────┤
│  2. 分析三句话：串行取最大，嵌套做乘法，  │
│     分支看最坏                          │
├─────────────────────────────────────────┤
│  3. 两层循环≠O(n²)，务必数内层实际次数   │
│     外层i*=2内层j<i → O(n)（等比求和）   │
├─────────────────────────────────────────┤
│  4. 递归：时间看节点总数，空间看树的深度  │
│     斐波那契递归：时间O(2ⁿ)，空间O(n)    │
├─────────────────────────────────────────┤
│  5. 快排最坏O(n²)（有序+端点基准），      │
│     归并/堆排序三者皆O(n log n)          │
├─────────────────────────────────────────┤
│  6. 归并排序空间O(n)（临时数组），        │
│     不是原地排序；堆排序空间O(1)          │
├─────────────────────────────────────────┤
│  7. 量级排序（慢→快）：                  │
│     O(1)<O(log n)<O(√n)<O(n)            │
│     <O(n log n)<O(n²)<O(n³)<O(2ⁿ)<O(n!) │
├─────────────────────────────────────────┤
│  8. C++ 1秒≈10⁸次操作：                  │
│     n≤10⁷→O(n), n≤10⁶→O(n log n),       │
│     n≤5000→O(n²), n≤200→O(n³),          │
│     n≤20→O(2ⁿ), n≤10→O(n!)              │
├─────────────────────────────────────────┤
│  9. 图邻接表遍历O(V+E)，邻接矩阵O(V²)     │
│     顶点+边是相加，不是相乘              │
├─────────────────────────────────────────┤
│ 10. DP时间=状态数×每状态转移代价          │
│     0/1背包O(nV)，区间DP O(n³)           │
├─────────────────────────────────────────┤
│ 11. 剪枝只改善实际运行，                  │
│     不改变最坏情况复杂度上界              │
├─────────────────────────────────────────┤
│ 12. 二分查找O(log n)的前提：数组有序      │
│     链表上二分退化为O(n)                 │
├─────────────────────────────────────────┤
│ 13. 计数/桶排序是非比较排序，O(n+k)，     │
│     靠空间换时间，k不能太大               │
├─────────────────────────────────────────┤
│ 14. 冒泡/插入最好O(n)的前提：             │
│     已有序+提前退出，裸写两层仍是O(n²)    │
└─────────────────────────────────────────┘