C / C++ / 系统课时

空间复杂度怎么算

空间复杂度怎么算

空间复杂度关注算法运行时额外占用了多少内存。分析时最容易混淆的是输入数组、局部变量、递归调用栈和临时缓冲区是否都要计算。先统一统计口径,再看峰值内存如何随 n 增长,就能得到可靠结论。

学习目标

  • 区分输入空间、总空间和辅助空间
  • 判断普通局部变量、递归调用栈和动态数组的空间复杂度
  • 根据运行期间的峰值内存而不是累计申请量判断复杂度

先确定统计口径

讨论算法空间复杂度时,最常见的是分析辅助空间复杂度,也就是不包含输入数据本身、算法为了完成计算额外使用的内存。若题目要求“总空间”,才需要把输入和输出占用也纳入计算。

例如处理一个长度为 n 的整数数组时,输入数组本身占 O(n)。如果算法只额外使用几个整数变量,则辅助空间为 O(1);如果又创建一个长度为 n 的临时数组,则辅助空间变成 O(n)。

内存来源 常见规模 辅助空间分析
输入数组 n 个元素 通常不计入
固定数量局部变量 与 n 无关 O(1)
长度为 n 的临时数组 随 n 增长 O(n)
深度为 n 的递归调用栈 n 个活动栈帧 O(n)

在题目没有额外说明时,可以明确采用“辅助空间”口径,避免把输入数组和算法自己申请的内存混在一起。

同样的计算结果可能使用不同空间

下面三个函数都处理同一个输入数组,但额外内存的增长方式不同:迭代求和只使用固定数量变量,递归求和会产生调用栈,复制函数则显式申请新的数组。

c
#include <stdio.h>
#include <stdlib.h>

int sum_iterative(const int *a, size_t n) {
    int total = 0;
    for (size_t i = 0; i < n; ++i) {
        total += a[i];
    }
    return total;
}

int sum_recursive(const int *a, size_t n) {
    if (n == 0) {
        return 0;
    }
    // 当前调用返回前,下一个递归调用的栈帧会继续存在。
    return a[n - 1] + sum_recursive(a, n - 1);
}

int *copy_array(const int *a, size_t n) {
    int *copy = malloc(n * sizeof *copy);
    if (n > 0 && copy == NULL) {
        return NULL;
    }

    for (size_t i = 0; i < n; ++i) {
        copy[i] = a[i];
    }
    return copy;
}

int main(void) {
    int data[] = {1, 2, 3, 4};
    size_t n = sizeof data / sizeof data[0];
    int *copy = copy_array(data, n);

    if (copy == NULL) {
        return 1;
    }

    printf("iterative: %d\n", sum_iterative(data, n));
    printf("recursive: %d\n", sum_recursive(data, n));
    printf("copied last: %d\n", copy[n - 1]);

    free(copy);
    return 0;
}

预期输出

text
iterative: 10
recursive: 10
copied last: 4

data 是输入,不计入辅助空间。sum_iterative 无论 n 多大,都只有 total、i 等固定数量变量,因此辅助空间是 O(1)。copy_array 申请 n 个整数的堆内存,所以辅助空间是 O(n)。

递归空间看最大调用深度

sum_recursive 没有显式创建数组,但递归调用也会占内存。计算 4 个元素时,调用过程会依次进入 sum_recursive(a, 4)、sum_recursive(a, 3),直到 sum_recursive(a, 0),前面的调用在结果返回前都还处于活动状态。

每个调用栈帧占用的空间可以视为常数,而最大同时存在的栈帧数量与 n 成正比,因此辅助空间为 O(n)。这里计算的是最大同时占用空间,而不是函数一共被调用了多少次。

这一区分尤其重要。某个递归算法可能执行指数级数量的函数调用,但如果任意时刻最多只有 O(n) 层递归,那么调用栈空间仍可能只是 O(n),时间复杂度和空间复杂度不必相同。

临时缓冲区按规模直接判断

显式创建的数组或动态内存通常最容易分析。如果临时空间的元素数量由 n 决定,就把元素数量转化成关于 n 的增长级别。

例如长度为 n 的临时数组需要 O(n) 空间,n×n 的临时矩阵需要 O(n²) 空间,而固定长度为 100 的缓冲区虽然实际占用更多字节,但它不会随 n 增长,因此渐进空间复杂度仍是 O(1)。

计算峰值而不是累计申请量

空间复杂度关心运行过程中某一时刻需要的最大内存。如果程序先申请一个 O(n) 缓冲区,释放后再申请另一个 O(n) 缓冲区,而两者不会同时存在,那么峰值仍是 O(n),不是 O(2n);即使写成 O(2n),忽略常数后也仍然是 O(n)。

判断空间复杂度时可以依次检查输入是否计入、局部变量数量是否随 n 增长、是否存在递归调用栈、是否申请临时数组或其他动态结构,最后取运行期间的最大同时占用量。这样就能把“用了多少变量”转化为真正与输入规模相关的空间增长关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

空间复杂度怎么算

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通