空间复杂度分析

概念讲解

常见空间复杂度

复杂度 示例
O(1) 常数个变量
O(n) 一维数组
O(n²) 二维数组
O(log n) 递归栈（二分）

存储单位

类型 大小
int 4 字节
long long 8 字节
double 8 字节
char 1 字节
bool 1 字节

内存计算

int a[1000][1000]
= 1000 * 1000 * 4 字节
= 4,000,000 字节
≈ 4 MB

考点分析

初赛考查方式

  1. 选择题： 空间计算
  2. 填空题： 内存占用

常见考点

  • 数组空间计算
  • 递归栈空间
  • 内存限制判断

例题精讲

例题 1：空间计算

题目： int a[1000] 占多少字节？

解答：

1000×4=40001000 \times 4 = 4000 字节

例题 2：内存限制

题目： 内存限制 256MB，能开 int a[10^7] 吗？

解答：

107×4=4×10710^7 \times 4 = 4 \times 10^7 字节 ≈ 40MB < 256MB，可以。

练习题

  1. long long a[100000] 占多少字节？
查看答案

800000 字节（约 0.76 MB）

100000×8=800000100000 \times 8 = 800000 字节

  1. 递归深度为 n 的空间复杂度是多少？
查看答案

O(n)

每次递归调用会在栈上分配空间，深度为 n 时，栈空间为 O(n)。

  1. 256MB 能开多大的 int 数组？
查看答案

约 6700 万个 int 元素

256×1024×1024/4=67108864256 \times 1024 \times 1024 / 4 = 67108864

实际可用约 6 × 10⁷ 个元素（需要留一些空间给其他变量和栈）。

易错点

⚠️ 注意：

  1. 1MB = 1024KB = 1048576B
  2. 递归有栈空间开销
  3. 全局数组在堆上，局部数组在栈上
  4. 竞赛通常内存限制 256MB 或 512MB