空间复杂度分析：内存的“账本”怎么算
聊完了时间复杂度，咱们得聊聊空间复杂度了。
说实话，我早年写代码的时候，对空间复杂度基本是“无视”的态度。那时候内存便宜，机器配置也高，总觉得“多用点内存怕什么”。直到有一次，我在嵌入式项目里栽了个跟头——一个递归函数把栈空间撑爆了，程序跑着跑着就崩了。从那以后，我才真正开始重视空间复杂度。
空间复杂度到底是什么？
空间复杂度，说白了就是你的程序运行时占用了多少内存。不是代码本身的大小，而是运行时额外开辟的空间。
你想想看，一个变量、一个数组、一次函数调用，都会消耗内存。空间复杂度就是衡量这些消耗的指标。
核心定义：空间复杂度 S(n) 表示随着输入规模 n 的增长，算法所需存储空间的增长趋势。
我习惯把空间开销分成三部分：
- 指令空间：代码本身占的空间，这个基本固定，不随输入变化
- 数据空间：存储常量和变量用的空间
- 栈帧空间：函数调用时压栈的空间，递归特别吃这个
我们分析空间复杂度时，主要关注的是额外空间——也就是除了输入数据本身之外，算法额外申请的空间。
常见空间复杂度一览
空间复杂度的级别和时间复杂度类似，也是用大O表示法。我整理了一张表，方便你对照：
| 级别 | 名称 | 典型场景 |
|---|---|---|
| O(1) | 常数空间 | 只用了几个临时变量，不随输入变化 |
| O(n) | 线性空间 | 复制了一个数组，或者用了哈希表 |
| O(n²) | 平方空间 | 二维矩阵、邻接矩阵 |
| O(log n) | 对数空间 | 递归深度为 log n 的二分查找 |
O(1) 常数空间：最省心的模式
这种算法只用了固定数量的变量。不管输入多大，内存占用都不变。
// 交换两个数，只用了一个临时变量
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}这个函数不管交换多大的数，都只用了 temp 这一个额外变量。空间复杂度就是 O(1)。
O(n) 线性空间：最常见的“代价”
很多算法需要额外复制一份数据，或者用哈希表存中间结果。这时候空间就跟着输入规模线性增长了。
// 数组反转，用了额外数组
int* reverseArray(int *arr, int n) {
int *newArr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
newArr[i] = arr[n - 1 - i];
}
return newArr;
}这里 newArr 的大小和输入数组一样，所以空间复杂度是 O(n)。
我的经验：很多初学者以为“用了数组就是 O(n)”，其实不一定。如果你只用了固定大小的数组（比如 int flags[10]），那还是 O(1)。关键看数组大小是否随输入变化。
O(n²) 平方空间：小心内存爆炸
这种场景常见于图算法中的邻接矩阵。n 个顶点，就需要 n×n 的矩阵来存边的关系。
// 邻接矩阵表示图
int **graph = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
graph[i] = (int*)malloc(n * sizeof(int));
}n=1000 时，这个矩阵就要占 4MB 左右。n=10000 时，直接 400MB。嗯，这里要注意，不是所有场景都适合用邻接矩阵。
O(log n) 对数空间：递归的“隐形杀手”
这个级别比较特殊。它通常来自递归调用时的栈空间。
// 二分查找的递归版本
int binarySearch(int arr[], int l, int r, int x) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}每次递归调用都会在栈上压一个帧。二分查找的递归深度是 log₂n，所以空间复杂度是 O(log n)。
我曾经踩过的坑：有一次我写了一个斐波那契数列的递归实现，n=50 的时候程序直接卡死了。为什么？因为递归深度是 n，空间复杂度 O(n)，栈空间被撑爆了。后来改成迭代版本，空间直接降到 O(1)。
时间与空间的权衡：鱼和熊掌
这是算法设计里最经典的话题了。说白了，很多时候你没法既要跑得快，又要省内存。
我举个例子你就明白了：
假设你要在一个数组里频繁查找某个元素。你有两个选择：
- 方案A：每次遍历查找，时间复杂度 O(n)，空间复杂度 O(1)
- 方案B：先排序，再用哈希表存索引，时间复杂度 O(1)，空间复杂度 O(n)
你看，这就是典型的“用空间换时间”。
我在做数据库索引优化的时候，就经常面临这种选择。索引能大幅提升查询速度，但每个索引都要额外占磁盘空间。怎么选？看业务场景。
我的建议：
- 嵌入式或移动端开发：优先省空间，内存金贵
- 服务器后端：优先省时间，响应速度是命根子
- 数据量小的时候：怎么简单怎么来，别过度优化
知识体系总览
下面这张图，把空间复杂度的核心脉络梳理了一遍。你可以把它当成一个“速查地图”：
总结一下
空间复杂度这东西，其实没那么玄乎。你只要记住：
- 先搞清楚哪些是“额外空间”
- 再看它跟输入规模 n 是什么关系
- 最后结合业务场景，决定是“省时间”还是“省空间”
我个人习惯是：写代码的时候先保证功能正确，然后看看空间占用是否在可接受范围内。如果内存吃紧，再考虑优化。别一开始就想着“我要用 O(1) 空间”，那样容易把自己绕进去。
好了，空间复杂度就聊到这儿。记住一句话：没有最好的算法，只有最合适的算法。
公众号:蓝海资料掘金营，微信deep3321