算法空间复杂度详解：概念与常见计算实例

算法在运行过程中不仅消耗时间，也占用内存。衡量算法好坏，除了时间复杂度，空间复杂度同样关键。它主要衡量算法运行所需的额外临时存储空间大小，通常用大 O 渐进表示法来描述。

注意，空间复杂度算的是变量的个数，而非程序占用的具体字节数。函数运行时所需的栈空间（参数、局部变量等）通常在编译期确定，因此重点在于显式申请的额外空间。

接下来通过几个典型场景，看看如何计算空间复杂度。

动态二维数组

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 到 n 列。总元素个数为 n(n+1)/2，根据大 O 推导规则，忽略低阶项和系数，空间复杂度为 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 == ) ;
    }
}