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

算法的空间复杂度

算法空间复杂度的定义是一个数学表达式，用于度量一个算法在运行过程中额外临时占用存储空间的大小。空间复杂度不是程序占用了多少字节的空间，而是计算变量的个数。其计算规则基本跟时间复杂度类似，也使用大 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;
}

解析：实例 1 在此处开辟的是一个二维数组，数组有 n 行，每行分别有 1, 2, 3, ..., 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;
    }
}

解析：实例 2 使用了常数个额外空间，分别是 end，exchange，i。根据大 O 阶的推导方法很容易得出，BubbleSort 空间复杂度为 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;
}

解析：实例 3 动态开辟了 N+1 个空间，根据大 O 阶的推导方法很容易得出，Fibonacci 空间复杂度为 O(N)。

实例四

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

解析：实例 4 递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)。

递归算法的空间复杂度 = 单次递归的空间复杂度 * 递归次数

全文总结

本文系统性地讲解了算法空间复杂度的核心知识，旨在帮助读者建立一套分析算法效率的完整框架。通过上述实例，可以清晰地理解不同数据结构及算法实现下的空间开销差异。