空间复杂度 O(n) = 算法执行过程中额外申请的存储空间，不包括输入数据
空间优化技术，从空间复杂度的角度进行空间优化时，顾名思义，就是让空间复杂度不复杂，思路就是极简：不额外申请，不留的销毁/释放，只留当前所需，不得不留的压缩。
什么是空间复杂度？
数组arr 有 1 亿个元素，都叫total。
那么，数组的空间复杂度：O(1)。
因为不管 arr 有 1 个元素还是 1 亿个，total 就一个变量。
for x in arr: total += x return total # 空间复杂度 O(1)：不管 arr 多大，total 始终一个变量包含一亿个 int的 数组：
- 空间复杂度（算法层面）：O(1)（没开新数组）
- 数组本身占用内存：1 亿 × 4 字节 = 400 MB（跟算法无关），实际占的物理空间叫footprint，不等于空间复杂度。
又开个等长数组呢？
空间复杂度变成O(1亿)了，因为额外开了个和输入一样大的数组。
def copy(arr): return [x for x in arr] # 空间复杂度 O(n)：额外开了一个等长数组算法的空间复杂度O(n)：就是给这个算法额外申请多大空间
快速排序的空间复杂度：O(log n)—— arr 是输入，不算；递归栈是额外开的，算。
随着递归分区，栈层数加深，后进先出，弹出后栈帧销毁，递归栈呆着的内存空间是额外申请的。
def quicksort(arr): quicksort_helper(arr, 0, len(arr)-1) # 递归栈给这个递归栈申请多大空间呢？
上面知道数组的空间复杂度是O(1)，分区1次，栈层数+1，平均情况下O(log n)层，那么快速排序需要的临时空间——平均空间复杂度就是O(log n)。最坏空间复杂度是O(n²）。
数据实际占的空间"有没有用？
有用！但它在另一个层面叫"内存占用 / footprint"，不叫"空间复杂度"。
工程上关心的几个真实指标：
| 指标 | 含义 | 例子 |
|---|---|---|
| 字面量空间 | 数据结构实际占的字节 | struct Node { int val; Node* next; }占 16 字节 |
| 空间复杂度 | 算法额外开的空间 | 递归栈、临时数组 |
| 驻留集（RSS） | 进程实际占的物理内存 | 看top命令 |
| 对象头开销 | 每个对象的元数据 | Java开销小，Python开销大 |
整个算法占用的空间≈数据结构实际占的字节+算法额外开的空间+进程实际占的物理内存+每个对象的元数据
常见算法 / 数据结构复杂度速查表
1、基础数据结构
| 数据结构 / 操作 | 时间（平均） | 时间（最坏） | 空间 | 适用场景 |
|---|---|---|---|---|
| 数组按下标访问 | O(1) | O(1) | O(n) | 随机访问 |
| 顺序查找 | O(n) | O(n) | O(1) | 无序线性查找 |
| 二分查找 | O(log n) | O(log n) | O(1) | 有序数组 |
| 冒泡 / 选择 / 插入排序 | O(n²) | O(n²) | O(1) | 小数据、教学 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定排序、大数据 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 通用排序首选 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 原地排序、Top K |
| 哈希表查找 | O(1) | O(n) | O(n) | 键值映射 |
| BST（二叉搜索树） | O(log n) | O(n) | O(n) | 有序数据 |
| AVL / 红黑树 | O(log n) | O(log n) | O(n) | 平衡有序 |
| B 树 / B+ 树 | O(log n) | O(log n) | O(n) | 磁盘存储、数据库索引 |
| 跳表 | O(log n) | O(n) | O(n) | 有序集合、Redis |
| Trie（前缀树） | O(m) | O(m) | O(Σ·m) | 字符串前缀、自动补全 |
| 并查集（路径压缩） | O(α(n)) ≈ O(1) | O(log n) | O(n) | 连通性问题 |
2、按问题选数据结构的决策树（速记）
同一个问题，不同数据结构空间差很多：存 1000 个点、10000 条边的图：
- 邻接表：O(V+E) = 1.1 万
- 邻接矩阵：O(V²) = 100 万
差了将近 100 倍，所以稀疏图千万别用邻接矩阵。
| 需求 | 选 |
|---|---|
| 查第 K 大 / 动态 Top K | 堆 |
| 范围求和 + 单点修改 | 树状数组 / 线段树 |
| 前缀匹配 | Trie |
| 连通性判断 | 并查集 |
| 最短路 | Dijkstra / SPFA |
| 字符串匹配 | KMP / Z 算法 |
| 区间最值 | ST 表 / 线段树 |
| 缓存 / 键值查找 | 哈希表 + LRU |
充分理解空间复杂度有什么用？
可以从空间复杂度角度进行空间优化。
空间优化思路是，极简不浪费！不额外申请，不留的销毁/释放，只留当前所需，不得不留的压缩。
常用的空间优化技术有：
- 滚动数组：在动态规划中只保留当前计算所需的前几行/列数据，而非整个二维表格，将空间从 O(n²) 降至 O(n)。
- 状态压缩：用位运算等技巧将多维状态压缩到一维，或将状态用整数表示，减少存储开销。
- 推导式 / 递推：数据边用边销毁，不保留中间完整副本，例如流式处理或迭代计算。
- 局部变量作用域：及时释放临时变量，避免不必要的长生命周期占用内存。
- 原地算法：直接在输入数据上修改，不额外申请等规模存储空间。
- 数据分块 / 懒加载：只加载当前需要处理的数据块，而非一次性载入全部数据。
@fivebliss
