空间复杂度

定义

空间复杂度 S(n) 表示算法所需存储空间与问题规模 n 的增长关系。分析时重点关注随 n 增长而变化的额外空间。

常量空间

如果算法运行所需额外空间不随问题规模变化，例如只使用少量局部变量，则 S(n) = O(1)。这种算法也称原地工作。

数组带来的空间

  • 一维数组 flag[n] 通常带来 O(n) 空间。
  • 二维数组 flag[n][n] 通常带来 O(n^2) 空间。
  • 若同时有 flag[n][n] 和 other[n]，总空间为 O(n^2) + O(n) + O(1) = O(n^2)。

递归调用带来的空间

递归会产生调用栈。每一层递归调用都需要保存参数、局部变量、返回地址等信息。

  • 若递归深度为 n，每层只使用常量空间，则递归调用的深度决定空间复杂度，S(n) = O(n)。
  • 若第 k 层还申请与 k 相关的空间，总空间要累加各层空间。例如每层使用规模依次为 1, 2, ..., n 的数组，则总空间为 O(n^2)，也可写成 O(n2)。

考点提示

时间复杂度看“执行次数如何增长”，空间复杂度看“额外存储如何增长”。程序代码本身和固定大小的常量、局部变量通常不影响渐进空间复杂度。

关联

空间复杂度常与 存储结构类型 一起考：顺序表存储密度高，链表需要额外指针域，静态链表需要游标数组。