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

算法的空间复杂度

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