C / C++ / 系统课时
空间复杂度怎么算
空间复杂度怎么算
空间复杂度关注算法运行时额外占用了多少内存。分析时最容易混淆的是输入数组、局部变量、递归调用栈和临时缓冲区是否都要计算。先统一统计口径,再看峰值内存如何随 n 增长,就能得到可靠结论。
学习目标
- 区分输入空间、总空间和辅助空间
- 判断普通局部变量、递归调用栈和动态数组的空间复杂度
- 根据运行期间的峰值内存而不是累计申请量判断复杂度
先确定统计口径
讨论算法空间复杂度时,最常见的是分析辅助空间复杂度,也就是不包含输入数据本身、算法为了完成计算额外使用的内存。若题目要求“总空间”,才需要把输入和输出占用也纳入计算。
例如处理一个长度为 n 的整数数组时,输入数组本身占 O(n)。如果算法只额外使用几个整数变量,则辅助空间为 O(1);如果又创建一个长度为 n 的临时数组,则辅助空间变成 O(n)。
| 内存来源 | 常见规模 | 辅助空间分析 |
|---|---|---|
| 输入数组 | n 个元素 | 通常不计入 |
| 固定数量局部变量 | 与 n 无关 | O(1) |
| 长度为 n 的临时数组 | 随 n 增长 | O(n) |
| 深度为 n 的递归调用栈 | n 个活动栈帧 | O(n) |
在题目没有额外说明时,可以明确采用“辅助空间”口径,避免把输入数组和算法自己申请的内存混在一起。
同样的计算结果可能使用不同空间
下面三个函数都处理同一个输入数组,但额外内存的增长方式不同:迭代求和只使用固定数量变量,递归求和会产生调用栈,复制函数则显式申请新的数组。
#include <stdio.h>
#include <stdlib.h>
int sum_iterative(const int *a, size_t n) {
int total = 0;
for (size_t i = 0; i < n; ++i) {
total += a[i];
}
return total;
}
int sum_recursive(const int *a, size_t n) {
if (n == 0) {
return 0;
}
// 当前调用返回前,下一个递归调用的栈帧会继续存在。
return a[n - 1] + sum_recursive(a, n - 1);
}
int *copy_array(const int *a, size_t n) {
int *copy = malloc(n * sizeof *copy);
if (n > 0 && copy == NULL) {
return NULL;
}
for (size_t i = 0; i < n; ++i) {
copy[i] = a[i];
}
return copy;
}
int main(void) {
int data[] = {1, 2, 3, 4};
size_t n = sizeof data / sizeof data[0];
int *copy = copy_array(data, n);
if (copy == NULL) {
return 1;
}
printf("iterative: %d\n", sum_iterative(data, n));
printf("recursive: %d\n", sum_recursive(data, n));
printf("copied last: %d\n", copy[n - 1]);
free(copy);
return 0;
}预期输出
iterative: 10
recursive: 10
copied last: 4data 是输入,不计入辅助空间。sum_iterative 无论 n 多大,都只有 total、i 等固定数量变量,因此辅助空间是 O(1)。copy_array 申请 n 个整数的堆内存,所以辅助空间是 O(n)。
递归空间看最大调用深度
sum_recursive 没有显式创建数组,但递归调用也会占内存。计算 4 个元素时,调用过程会依次进入 sum_recursive(a, 4)、sum_recursive(a, 3),直到 sum_recursive(a, 0),前面的调用在结果返回前都还处于活动状态。
每个调用栈帧占用的空间可以视为常数,而最大同时存在的栈帧数量与 n 成正比,因此辅助空间为 O(n)。这里计算的是最大同时占用空间,而不是函数一共被调用了多少次。
这一区分尤其重要。某个递归算法可能执行指数级数量的函数调用,但如果任意时刻最多只有 O(n) 层递归,那么调用栈空间仍可能只是 O(n),时间复杂度和空间复杂度不必相同。
临时缓冲区按规模直接判断
显式创建的数组或动态内存通常最容易分析。如果临时空间的元素数量由 n 决定,就把元素数量转化成关于 n 的增长级别。
例如长度为 n 的临时数组需要 O(n) 空间,n×n 的临时矩阵需要 O(n²) 空间,而固定长度为 100 的缓冲区虽然实际占用更多字节,但它不会随 n 增长,因此渐进空间复杂度仍是 O(1)。
计算峰值而不是累计申请量
空间复杂度关心运行过程中某一时刻需要的最大内存。如果程序先申请一个 O(n) 缓冲区,释放后再申请另一个 O(n) 缓冲区,而两者不会同时存在,那么峰值仍是 O(n),不是 O(2n);即使写成 O(2n),忽略常数后也仍然是 O(n)。
判断空间复杂度时可以依次检查输入是否计入、局部变量数量是否随 n 增长、是否存在递归调用栈、是否申请临时数组或其他动态结构,最后取运行期间的最大同时占用量。这样就能把“用了多少变量”转化为真正与输入规模相关的空间增长关系。