算法的空间复杂度
算法在运行过程中需要消耗时间资源和空间资源。衡量一个算法的好坏，通常从时间和空间两个维度来考量，即时间复杂度和空间复杂度。
时间复杂度主要衡量算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。虽然现代计算机存储容量已大幅提升，不再像早期那样对空间极度敏感，但在设计高性能算法时，空间效率依然是关键指标。
核心定义
算法空间复杂度的定义：
- 它是一个数学表达式，用于度量算法在运行过程中额外临时占用存储空间的大小。
- 注意：它不是程序占用了多少 bytes 的空间（这个意义不大），而是算变量的个数。
- 计算规则基本跟时间复杂度类似，也使用大 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;
}
解析：
这里开辟的是一个二维数组结构。外层循环执行 n 次，内层每次分配的列数不同，分别是 1, 2, 3, ..., n 列。
总元素个数为 1 + 2 + ... + n，即 n(n + 1) / 2。
根据大 O 阶推导方法，忽略低阶项和系数，空间复杂度为 O(n²)。
2. 冒泡排序 (Bubble Sort)
void BubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = ;
( i = ; i < end; ++i) {
(a[i - ] > a[i]) {
(&a[i - ], &a[i]);
exchange = ;
}
}
(exchange == ) ;
}
}
