算法的空间复杂度
算法运行时，除了时间，还会占用一部分空间。做算法分析时，时间复杂度大家看得多，空间复杂度往往容易被顺手带过，但在内存吃紧、递归层数深，或者要做大规模数据处理时，它一点也不轻。
空间复杂度主要看的是算法额外占用的存储空间，不是程序最终一共用了多少内存。后者受运行环境、编译器、库函数影响太大，拿来比较没什么意义。我们真正关心的是：输入规模变大时，额外空间怎么涨。
核心定义
算法空间复杂度通常写成一个数学表达式，用来描述算法在运行过程中额外临时占用的存储空间规模。
- 关注的是额外空间，不是输入本身占了多少。
- 计算时通常按变量个数、递归栈深度、动态申请的空间来估算。
- 表达方式和时间复杂度一样，一般也用大 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;
( i = ; i < end; ++i) {
(a[i - ] > a[i]) {
(&a[i - ], &a[i]);
exchange = ;
}
}
(exchange == ) ;
}
}
