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

算法在运行过程中不仅消耗时间，也占用内存。衡量算法好坏，除了时间复杂度，空间复杂度同样关键。它主要衡量算法运行所需的额外临时存储空间大小，通常用大 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 == 0) break;
    }
}

原地排序算法通常不需要额外开辟大量空间。这里只使用了 end、exchange、i 等常数个辅助变量，所以空间复杂度是 O(1)。

斐波那契数列

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 类型的空间，随着 n 线性增长，空间复杂度为 O(n)。

递归调用

long long Fac(size_t N) {
    if (N == 0) return 1;
    return Fac(N - 1) * N;
}

递归的深度决定了栈帧的数量。这里调用了 N 次，每个栈帧占用常数空间，因此空间复杂度为 O(N)。一般规律是：递归算法的空间复杂度 = 单次递归的空间复杂度 × 递归次数。

掌握空间复杂度的核心在于识别额外申请的空间来源，无论是动态内存还是递归栈帧。理解这些有助于编写更高效的程序。