第2章：算法分析（Algorithm Analysis）
一、导读
1.1 本章学习目标
第2章在第1章的基础上，系统深入地讲解算法分析的方法和工具。如果说第1章让你知道了"什么是复杂度"，那么本章将教你"如何精确计算复杂度"。你将学习如何处理各种复杂的代码结构——嵌套循环、递归调用、分治算法——并掌握求解递归方程的数学工具。
本章的核心学习目标包括：
- 掌握时间复杂度分析的系统方法：如何对任意代码结构精确计算时间复杂度？
- 理解空间复杂度的概念：算法除了时间，还需要多少额外内存空间？
- 区分最坏、最好和平均情况分析：三种分析方式各有什么意义和局限？
- 学会求解递归方程：代入法、递归树法、主方法（Master Theorem）分别适用于什么场景？
- 理解常见复杂度等级的实际含义：O(n) 和 O(n log n) 在实际问题中意味着什么？
- 通过经典问题（最大子序列和）巩固分析技能：四种不同复杂度的解法如何推导？
1.2 为什么第二章如此重要
算法分析是数据结构课程的"数学基础"。在后续章节中，每引入一种新的数据结构，都需要分析其操作的复杂度。如果你不能熟练地进行复杂度分析，就无法判断哪种数据结构更适合你的应用场景。
本章介绍的递归方程求解方法尤其重要——因为后续章节中大量数据结构（树、堆、分治算法）的运行时间都自然地以递归形式出现。掌握主方法和递归树法，你就能快速分析递归算法的效率。
此外，本章通过最大子序列和问题的四种解法，展示了"同一个问题可以有截然不同的算法效率"这一核心思想。这种从 O(n³) 到 O(n) 的优化过程，是算法设计思维的经典训练。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
对于嵌套循环，什么时候复杂度是 O(n²)，什么时候是 O(n log n)？
递归方程 T(n) = 2T(n/2) + O(n) 的解是什么？它对应什么算法？
"平均情况分析"为什么比"最坏情况分析"困难得多？
一个算法的空间复杂度为 O(n)，这意味着什么？
为什么 O(n log n) 是基于比较的排序算法的理论下界？
如何分析一个既有循环又有递归的算法的复杂度？
二、核心概念详解
2.1 时间复杂度分析的系统方法
时间复杂度分析的核心是计数基本操作的执行次数。我们通常选择一种"基本操作"（如比较、赋值、加法），然后计算算法执行该操作的总次数关于输入规模 n 的函数。
2.1.1 简单循环的分析
c
// 例1：单层循环 - O(n)
for (int i = 0; i < n; i++) // 执行n次
printf("%d\n", i); // 每次O(1)
// 总计：n × O(1) = O(n)
// 例2：步长不为1的循环 - O(log n)
for (int i = 1; i < n; i *= 2) // i = 1, 2, 4, 8, ..., 2^k
printf("%d\n", i);
// 循环次数k满足 2^k = n，即 k = log₂n
// 总计：O(log n)
// 例3：嵌套循环，内外独立 - O(n²)
for (int i = 0; i < n; i++) // n次
for (int j = 0; j < n; j++) // n次
printf("%d %d\n", i, j);
// 总计：n × n = n² = O(n²)
// 例4：嵌套循环，内层依赖外层 - 仍是O(n²)
for (int i = 0; i < n; i++) // n次
for (int j = i; j < n; j++) // n-i次
printf("%d %d\n", i, j);
// 总计：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)
// 例5：内外层不同的嵌套循环
for (int i = 0; i < n; i++) // n次
for (int j = 0; j < m; j++) // m次
printf("%d %d\n", i, j);
// 总计：O(n × m)，当 n = m 时为 O(n²)2.1.2 复杂代码结构的分析
c
// 例6：循环后接循环 - 取最大值
for (int i = 0; i < n; i++) // O(n)
sum += i;
for (int i = 0; i < n; i++) // O(n)
for (int j = 0; j < n; j++) // O(n²)
sum += i * j;
// 总计：O(n) + O(n²) = O(n²)
// 例7：if-else结构 - 取较大分支
if (condition) {
// O(n) 的操作
for (int i = 0; i < n; i++)
sum += i;
} else {
// O(n²) 的操作
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += i * j;
}
// 最坏情况：O(n²)
// 例8：对数步长的嵌套
for (int i = 1; i < n; i *= 2) { // log n次
for (int j = 0; j < n; j++) { // n次
sum += j;
}
}
// 总计：O(n log n)2.2 空间复杂度分析
空间复杂度描述算法运行所需的额外内存空间关于输入规模的增长趋势。需要注意的是，空间复杂度通常只计算额外空间（auxiliary space），不包括输入数据本身占用的空间。
c
// 例1：O(1) 额外空间
int sum(int arr[], int n) {
int total = 0; // 只需要常数个变量
for (int i = 0; i < n; i++)
total += arr[i];
return total;
}
// 空间复杂度：O(1)
// 例2：O(n) 额外空间
void mergeSort(int arr[], int temp[], int n) {
// 归并排序需要一个与原数组等大的临时数组
if (n < 2) return;
// ... 分割、排序、合并 ...
// temp数组占用O(n)额外空间
}
// 空间复杂度：O(n)
// 例3：O(n) 递归栈空间
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // 递归深度为n
}
// 每次调用占用O(1)栈空间，总共O(n)层
// 空间复杂度：O(n)（递归栈）2.3 最坏、最好与平均情况
对于同一个算法，不同的输入可能导致不同的运行时间。我们需要区分三种情况：
- 最坏情况（Worst Case）：在所有可能的输入中，算法运行时间的上界。这是最常用的分析方式，因为它提供了性能保证。
- 最好情况（Best Case）：在所有可能的输入中，算法运行时间的下界。通常意义不大，因为它不能提供任何保证。
- 平均情况（Average Case）：对所有可能输入的运行时间取期望值。这最有实际意义，但分析通常最困难。
c
// 线性搜索的三种情况分析
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) // 找到了
return i;
}
return -1; // 没找到
}
// 最坏情况：key不在数组中，需要检查所有n个元素 → O(n)
// 最好情况：key在第一个位置，只需检查1个元素 → O(1)
// 平均情况：假设key等概率出现在任意位置或不存在
// E[比较次数] = (1/n+1)(1 + 2 + ... + n + n) = (n+1)/2 + n/(n+1)
// 约等于 n/2 → 仍然是 O(n)2.4 递归方程的求解
递归算法的时间复杂度通常以递归方程（递推关系）的形式出现。求解这些方程是分析递归算法的关键。
2.4.1 代入法（Substitution Method）
先猜测解的形式，然后用数学归纳法证明。
例：T(n) = 2T(n/2) + O(n)
猜测：T(n) = O(n log n)
证明：假设 T(k) ≤ c·k·log k 对所有 k < n 成立
T(n) ≤ 2·c·(n/2)·log(n/2) + d·n
= c·n·(log n - 1) + d·n
= c·n·log n - c·n + d·n
= c·n·log n + (d - c)·n
取 c ≥ d，则 T(n) ≤ c·n·log n = O(n log n) ✓2.4.2 递归树法（Recursion Tree Method）
将递归展开为一棵树，计算每层的代价，然后求和。
例：T(n) = 2T(n/2) + O(n)
第0层： cn → cn
第1层： cn/2 cn/2 → cn
第2层： cn/4 cn/4 cn/4 cn/4 → cn
...
第log n层： c c c c ... c c c c → cn（共n个叶子）
总层数：log n + 1
每层代价：cn
总计：cn × (log n + 1) = O(n log n)2.4.3 主方法（Master Theorem）
主方法提供了形如 T(n) = aT(n/b) + O(nᵈ) 的递归方程的直接求解公式。
主定理：对于 T(n) = aT(n/b) + O(nᵈ)，其中 a ≥ 1, b > 1, d ≥ 0：
- 若 log_b(a) > d，则 T(n) = O(n^(log_b(a)))
- 若 log_b(a) = d，则 T(n) = O(nᵈ log n)
- 若 log_b(a) < d，则 T(n) = O(nᵈ)
例1：T(n) = 2T(n/2) + O(n)
a=2, b=2, d=1
log₂(2) = 1 = d → T(n) = O(n log n)
例2：T(n) = 4T(n/2) + O(n)
a=4, b=2, d=1
log₂(4) = 2 > d=1 → T(n) = O(n²)
例3：T(n) = 2T(n/2) + O(n²)
a=2, b=2, d=2
log₂(2) = 1 < d=2 → T(n) = O(n²)
例4：T(n) = T(n/2) + O(1)（二分查找）
a=1, b=2, d=0
log₂(1) = 0 = d → T(n) = O(log n)2.5 最大子序列和问题的四种解法
这个问题是算法分析的经典案例，展示了同一个问题如何从 O(n³) 优化到 O(n)。
c
// 解法1：暴力枚举所有子序列 - O(n³)
// 三层循环：枚举起点i、终点j、计算和
int maxSubSum1(const int a[], int n) {
int maxSum = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
int thisSum = 0;
for (int k = i; k <= j; k++)
thisSum += a[k];
if (thisSum > maxSum)
maxSum = thisSum;
}
return maxSum;
}
// 分析：Σ(i=0→n-1) Σ(j=i→n-1) (j-i+1) = O(n³)
// 解法2：优化内层求和 - O(n²)
// 关键观察：a[i..j]的和 = a[i..j-1]的和 + a[j]
int maxSubSum2(const int a[], int n) {
int maxSum = 0;
for (int i = 0; i < n; i++) {
int thisSum = 0;
for (int j = i; j < n; j++) {
thisSum += a[j]; // 累加而非重新计算
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
// 分析：消除了最内层循环 → O(n²)
// 解法3：分治法 - O(n log n)
// 将数组分为两半，最大子序列要么在左半、右半、或跨越中点
int maxSubSum3(const int a[], int left, int right) {
if (left == right)
return a[left] > 0 ? a[left] : 0;
int center = (left + right) / 2;
int maxLeftSum = maxSubSum3(a, left, center);
int maxRightSum = maxSubSum3(a, center + 1, right);
int maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--) {
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
int maxRightBorderSum = 0, rightBorderSum = 0;
for (int i = center + 1; i <= right; i++) {
rightBorderSum += a[i];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
int max1 = maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
int max2 = maxLeftBorderSum + maxRightBorderSum;
return max1 > max2 ? max1 : max2;
}
// 递归方程：T(n) = 2T(n/2) + O(n)
// 由主定理：a=2, b=2, d=1, log₂2=1=d → O(n log n)
// 解法4：Kadane算法（在线算法）- O(n)
int maxSubSum4(const int a[], int n) {
int maxSum = 0, thisSum = 0;
for (int i = 0; i < n; i++) {
thisSum += a[i];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
// 分析：单层循环 → O(n)
// 关键洞察：负的子序列和不可能对后续产生正贡献三、实战案例
3.1 分析递归算法的复杂度
c
// 例1：二分查找 - O(log n)
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// 每次迭代将搜索范围减半
// T(n) = T(n/2) + O(1)
// 由主定理：a=1, b=2, d=0, log₂1=0=d → O(log n)
// 例2：归并排序 - O(n log n)
void mergeSort(int arr[], int temp[], int left, int right) {
if (left >= right) return; // O(1)
int mid = (left + right) / 2; // O(1)
mergeSort(arr, temp, left, mid); // T(n/2)
mergeSort(arr, temp, mid+1, right); // T(n/2)
merge(arr, temp, left, mid, right); // O(n)
}
// T(n) = 2T(n/2) + O(n)
// 由主定理：a=2, b=2, d=1, log₂2=1=d → O(n log n)
// 例3：快速排序 - 平均O(n log n)，最坏O(n²)
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // O(n)
quickSort(arr, low, pi - 1); // T(k)
quickSort(arr, pi + 1, high); // T(n-k-1)
}
}
// 最坏情况（已排序数组，pivot选最后一个）：
// T(n) = T(n-1) + O(n) → O(n²)
// 平均情况（pivot均匀分割）：
// T(n) = 2T(n/2) + O(n) → O(n log n)
// 例4：斐波那契递归 - O(2ⁿ)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// T(n) = T(n-1) + T(n-2) + O(1)
// 这个递归方程的解约为 O(1.618ⁿ) ≈ O(2ⁿ)
// 原因：大量重复计算3.2 空间复杂度分析实例
c
// 例1：原地反转数组 - O(1)空间
void reverse(int arr[], int n) {
for (int i = 0; i < n / 2; i++) {
int temp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = temp;
}
}
// 只用了1个临时变量 → O(1)
// 例2：复制数组 - O(n)空间
int *copyArray(int arr[], int n) {
int *copy = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
copy[i] = arr[i];
return copy;
}
// 分配了n个int的空间 → O(n)
// 例3：递归的空间开销
void recursivePrint(int n) {
if (n <= 0) return;
int local = n; // 每层O(1)局部变量
printf("%d\n", local);
recursivePrint(n - 1); // 递归n层
}
// 递归栈深度为n，每层O(1) → 空间O(n)四、本章小结
本章系统讲解了算法分析的方法和工具：
时间复杂度分析的核心是计数基本操作的执行次数。掌握循环分析、嵌套循环分析和递归分析的基本方法，是评估算法效率的基础。
空间复杂度衡量算法运行所需的额外内存。递归算法的空间复杂度通常由递归栈深度决定。
三种分析方式各有用途：最坏情况分析提供性能保证，平均情况分析最贴近实际但最难推导，最好情况通常参考意义不大。
递归方程求解是分析递归算法的关键工具。代入法适合验证猜测，递归树法直观易懂，主方法提供了特定形式方程的直接求解公式。
最大子序列和问题的四种解法生动展示了算法优化的力量：从 O(n³) 到 O(n)，每一步优化都基于对问题更深层次的理解。
五、思考与练习
思考题
证明：对于任何基于比较的排序算法，最坏情况下至少需要 O(n log n) 次比较。（提示：考虑决策树模型）
分析以下递归方程的复杂度：
- T(n) = 3T(n/3) + O(n)
- T(n) = T(n-1) + O(n)
- T(n) = 2T(n/2) + O(1)
为什么快速排序的平均情况是 O(n log n) 但最坏情况是 O(n²)？如何通过随机化避免最坏情况？
编程练习
实现一个 O(log n) 的幂函数 power(x, n)，计算 x 的 n 次幂。
编写程序测量不同规模输入下 O(n)、O(n log n)、O(n²) 算法的实际运行时间，验证理论分析。
实现最大子序列和的四种算法，在相同数据上对比运行时间。