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

2. 冒泡排序

// 计算 BubbleSort 的空间复杂度？
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 等几个变量。无论输入规模 n 多大，额外申请的空间都是固定的。根据大 O 阶推导方法，空间复杂度为 O(1)。

3. 斐波那契数列（非递归）

// 计算 Fibonacci 的空间复杂度？
// 返回斐波那契数列的前 n 项
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 类型的空间用于存储数列。根据大 O 阶推导方法，空间复杂度为 O(N)。

4. 阶乘递归

// 计算阶乘递归 Fac 的空间复杂度？
long long Fac(size_t N) {
    if (N == 0) return 1;
    return Fac(N - 1) * N;
}

解析： 递归调用了 N 次，每次调用都会在栈上开辟一个新的栈帧。每个栈帧使用了常数个空间（保存 N 和返回地址等）。总共开辟了 N 个栈帧，因此空间复杂度为 O(N)。

🎯 递归算法的空间复杂度 = 单次递归的空间复杂度 × 递归深度

总结

本文系统性地讲解了算法空间复杂度的核心知识，旨在帮助读者建立一套分析算法效率的完整框架。通过对比不同场景下的代码实现，可以看出空间复杂度的计算关键在于统计额外临时占用的变量个数或内存块大小。掌握这些规则，有助于在实际开发中写出更节省资源的程序。