空间复杂度

一句话理解

空间复杂度描述多用了多少内存随 n 的增长。

为什么要学

开 DP 表、递归栈、大数组都要算。

讲解

O(1) 额外空间表示只用了几个变量。O(n) 常是一个长度为 n 的数组。

时间和空间常常互换：预处理更多，查询更快。

例子

int a[n] 是 O(n) 空间。int a[n][n] 是 O(n²) 空间。

常见错误

• 只估时间不估空间，5000² 的 int 表可能 MLE。
• 忽略递归深度占用的栈。