算法的空间复杂度
算法运行时，除了时间，还会占用一部分空间。做算法分析时，时间复杂度大家看得多，空间复杂度往往容易被顺手带过，但在内存吃紧、递归层数深，或者要做大规模数据处理时，它一点也不轻。
空间复杂度主要看的是算法额外占用的存储空间，不是程序最终一共用了多少内存。后者受运行环境、编译器、库函数影响太大，拿来比较没什么意义。我们真正关心的是：输入规模变大时，额外空间怎么涨。
核心定义
算法空间复杂度通常写成一个数学表达式，用来描述算法在运行过程中额外临时占用的存储空间规模。
- 关注的是额外空间，不是输入本身占了多少。
- 计算时通常按变量个数、递归栈深度、动态申请的空间来估算。
- 表达方式和时间复杂度一样，一般也用大 O 表示法。
函数运行时的栈空间也算在内。参数、局部变量、返回地址这些内容，通常会随着递归深度或调用层数变化，不能直接忽略。
常见空间复杂度计算示例
下面几个例子，基本能覆盖日常最常见的几种情况。
1. 动态二维数组分配
int** fun(int n) {
int** s = (int**)malloc(n * sizeof(int*));
for (size_t i = 0; i < n; ++i) {
s[i] = (int*)malloc((i + 1) * sizeof(int));
}
return s;
}
这里申请的是一个'行数递增'的二维数组。第 1 行 1 个元素，第 2 行 2 个元素，一直到第 n 行。
总元素个数是 1 + 2 + ... + n，结果是 n(n + 1) / 2。去掉常数和低阶项以后，空间复杂度就是 O(n²)。
2. 冒泡排序
void BubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = 0;
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0) break;
}
}
这个实现是原地排序，额外只用了 end、exchange、i 这几个变量。它们的数量不会随着 n 变大而增加，所以空间复杂度是 O(1)。
3. 斐波那契数列
long long* Fibonacci(size_t n) {
if (n == 0) return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; ++i) {
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}
这里直接申请了 n + 1 个 long long 空间来保存结果。输入规模越大，数组越长，空间也按线性增长，所以复杂度是 O(N)。
4. 递归阶乘
long long Fac(size_t N) {
if (N == 0) return 1;
return Fac(N - 1) * N;
}
递归函数看起来代码很短，空间账却不便宜。它会一路调用到 N == 0，调用栈上会压下 N 层栈帧。每层栈帧消耗的空间是常数级，所以总空间复杂度是 O(N)。
递归的空间复杂度，通常看的是'递归深度 × 单层栈帧开销'。这个判断比只看代码长度靠谱得多。
实际分析时怎么想
我一般先分两类看：一类是显式申请的堆空间，比如 malloc、new；另一类是函数调用带来的栈空间，尤其是递归。前者比较直观，后者经常被漏掉，但线上出问题时往往就是它先顶不住。
同样的功能，写法不同，空间占用可能差很多。能原地做的就别多开数组；递归写起来顺手，但如果递归层数会很深，最好提前想清楚栈会不会扛不住。这个取舍没有标准答案，要看数据规模和运行环境。
小结
空间复杂度主要看额外空间，而不是程序最终占了多少内存。分析时重点关注动态申请的存储、递归带来的栈帧，以及那些会随输入规模增长的数据结构。像冒泡排序这种原地算法，额外空间是常数；像动态二维数组、递归阶乘这类实现，空间会随着 n 明显增长。实际写代码时，时间和空间很少能同时占优，通常得按场景选一个更合适的平衡点。
