第66章 算法的时间和空间效率分析

衡量一个算法"快不快、占不占内存"，靠的不是跑一次看秒表，而是渐进复杂度——即输入规模 $n$ 变大时，运行时间/内存如何增长。八级要求"能分析排序、查找、树图遍历、搜索、分治、动态规划等各类算法的时间和空间复杂度，并据此优化"。

66.1 复杂度分析方法

66.1.1 时间复杂度分析方法

1. 找出算法中的基本操作：赋值、比较、算术运算等与问题规模强相关的操作。
2. 统计基本操作总执行次数，记为函数$T(n)$，$n$为输入规模。
3. 简化：仅保留最高阶项、丢弃系数，得到时间复杂度。

66.1.2 空间复杂度分析方法

1. 统计程序占用所有存储空间：输入、代码、常量、临时变量、数组、栈等。
2. 提取随$n$变化的存储开销，记$S(n)$。
3. 简化得到空间复杂度，只保留最高阶项。

66.2 各类算法复杂度分析

66.2.1 排序算法

冒泡排序

• 时间复杂度：平均、最坏$O(n^2)$；完全有序最优$O(n)$
• 空间复杂度：$O(1)$，仅交换临时变量

快速排序

• 时间复杂度：平均$O(n\log n)$；数组有序/逆序最坏$O(n^2)$
• 空间复杂度：$O(\log n)$（递归栈深度），最坏$O(n)$

归并排序

• 时间复杂度：最优/平均/最坏统一$O(n\log n)$
• 空间复杂度：$O(n)$，需要辅助数组存储合并结果

66.2.2 查找算法

顺序查找

• 时间：最好$O(1)$，平均/最坏$O(n)$
• 空间：$O(1)$

二分查找

• 时间：最好$O(1)$，平均/最坏$O(\log n)$
• 空间：迭代$O(1)$；递归$O(\log n)$（递归栈）

66.2.3 树遍历（前/中/后序）

• 时间复杂度：$O(n)$，每个节点访问一次
• 空间复杂度：$O(h)$，$h$为树高；平衡树$O(\log n)$，斜树$O(n)$

66.2.4 图遍历 DFS / BFS

• 时间复杂度：$O(V+E)$，$V$顶点数，$E$边数
• 空间复杂度：$O(V)$（栈/队列、访问标记数组）

66.2.5 暴力深度/广度搜索（迷宫等）

• 时间：$O(b^d)$，$b$分支数，$d$搜索深度
• 空间：$O(b^d)$

66.2.6 分治算法

递推式$T(n)=k \cdot T(n/k)+D(n)+C(n)$，归并排序是典型例子，时间$O(n\log n)$。

66.2.7 动态规划

• 一维DP：时间$O(n)$
• 二维DP（LCS、区间DP）：时间$O(n^2)$
• Floyd图全最短路：$O(n^3)$ 空间可通过滚动数组从$O(n^2)$压缩至$O(n)$

66.3 复杂度等级从快到慢

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < 2^n$

66.4 真题示例（根据数据范围选算法）

【GESP 八级风格·选择题变形】 某题输入规模 $n \le 100000$，时限 1 秒（一般 1 秒约可安全执行 $10^8$ 次基本操作）。下列哪个做法最可能超时？

• A. $O(n)$ 遍历一遍
• B. $O(n \log n)$ 排序后处理
• C. $O(n^2)$ 双重循环
• D. $O(n \log n)$ 用优先队列求最值

分析与解答： 估算各做法在 $n=10^5$ 时的操作数：

• A：$10^5$ 次 —— 轻松通过；
• B/C 中的 $n\log n \approx 10^5 \times 17 \approx 1.7\times10^6$ 次 —— 通过；
• C：$n^2 = 10^{10}$ 次 —— 远超 $10^8$，必然超时。

因此选 C。这也是八级"算法优化"章节的核心动机：把 $O(n^2)$ 优化到 $O(n\log n)$ 往往就是"过与不过"的分界线。

附：读代码判复杂度的迷你练习

int cnt = 0;
for (int i = 1; i <= n; ++i)        // 外层 n 次
    for (int j = 1; j <= n; ++j)    // 内层 n 次
        cnt++;                      // 基本操作

双重嵌套、每层都与 $n$ 相关，总次数 $n \times n = n^2$，时间复杂度为 $O(n^2)$；只用了常数个变量，空间复杂度 $O(1)$。

练习题

1.（等级） 下列复杂度从快到慢（最优→最差）排列，正确的是？

• A. $O(n) < O(\log n) < O(n^2)$
• B. $O(\log n) < O(n) < O(n^2)$
• C. $O(n^2) < O(n) < O(\log n)$
• D. $O(n) < O(n^2) < O(\log n)$

2.（排序） 归并排序的时间复杂度是？

• A. 平均 $O(n^2)$，最坏 $O(n^2)$
• B. 统一 $O(n\log n)$
• C. 平均 $O(n\log n)$，最坏 $O(n^2)$
• D. $O(n)$

3.（查找） 在已排序数组中用二分查找，时间复杂度是？

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n^2)$
• D. $O(1)$

4.（读代码） 下面代码的时间复杂度是？

for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j)
        sum++;

• A. $O(n)$
• B. $O(n\log n)$
• C. $O(n^2)$
• D. $O(n^3)$

5.（图遍历） DFS / BFS 遍历一个 $V$ 个顶点 $E$ 条边的图，时间复杂度是？

• A. $O(V)$
• B. $O(E)$
• C. $O(V+E)$
• D. $O(V \times E)$