相关内容地址：算法复杂度分析 —形式化的均摊复杂度证明和 Master 定理示例（2）
一、常见空间复杂度（Space Complexity）
空间复杂度衡量算法额外占用的内存大小随输入规模 n 的增长关系。
常见阶如下：
| 空间复杂度 | 说明 | 示例 |
|---|---|---|
| O ( 1 ) O(1)O(1)常数空间 | 不随 n 增长 | 双指针、原地排序部分步骤 |
| O ( log n ) O(\log n)O(logn) | 通常来自递归深度 | 二分查找、平衡树操作 |
| O ( n ) O(n)O(n) | 线性辅助数组/链表/栈 | BFS 队列、前缀和数组 |
| O ( n log n ) O(n\log n)O(nlogn) | 分治产生多个子结构 | 归并排序递归树的额外空间 |
| O ( n 2 ) O(n^2)O(n2) | 二维矩阵、DP 表 | Floyd、棋盘 DP |
| O ( 2 n ) O(2^n)O(2n) | 状态压缩枚举 | 子集枚举、回溯状态树 |
| O ( n ! ) O(n!)O(n!) | 全排列空间 | 回溯输出所有排列 |
补充：
- “input size” 不算空间复杂度
- 重点分析额外空间（auxiliary space）
二、实际代码示例分析
示例 1：双指针（常数空间O ( 1 ) O(1)O(1)）
inttwoSumClosest(vector<int>&a){intl=0,r=a.size()-1;intbest=INT_MAX;while(l<r){intsum=a[l]+a[r];best=min(best,abs(sum));if(sum>0)r--;elsel++;}returnbest;}空间复杂度
- 只用了
l, r, best等常量变量 →O ( 1 ) O(1)O(1)
示例 2：递归 DFS（空间O ( n ) O(n)O(n)）
voiddfs(intu,vector<vector<int>>&g,vector<bool>&vis){vis[u]=true;// 共享内存，不算额外空间for(intv:g[u])if(!vis[v])dfs(v,g,vis);}空间复杂度
- 递归深度最深可能 = n
→ 栈空间O ( n ) O(n)O(n) - 额外空间取决于图形结构，不包括输入图本身
示例 3：归并排序（O ( n ) O(n)O(n)）
归并需要临时数组：
voidmerge(vector<int>&a,intl,intr){vector<int>tmp(r-l+1);// 临时空间 O(n)...}→ 额外空间 =O ( n ) O(n)O(n)
（注意：递归深度O ( log n ) O(\log n)O(logn)，但临时数组占主导）
三、复杂度分析技巧
1. 循环分析法则（非常常用）
(1) 单层循环
for(inti=0;i<n;i++){// O(1)}空间：O ( 1 ) O(1)O(1)
时间 = 循环次数 × 循环体耗时 =n ⋅ O ( 1 ) = O ( n ) n \cdot O(1) = O(n)n⋅O(1)=O(n)
(2) 嵌套循环 = 循环次数的乘积
for(inti=0;i<n;i++)for(intj=0;j<n;j++)...时间：O ( n 2 ) O(n^2)O(n2)
空间：O ( 1 ) O(1)O(1)
(3) 递归算法
空间 =递归深度 × 每帧额外空间
例如：
intf(intn){if(n==1)return1;returnf(n-1)+f(n-2);}深度 = n
每帧空间 = 常数
→ 总空间O ( n ) O(n)O(n)
2. 递归（Recursion）空间复杂度分析步骤
递归空间来自调用栈（call stack）。
通用步骤：
Step 1：写出递归深度
例如：
- 二分：深度log n \log nlogn
- 线性递归：深度n nn
- 分治树：深度log n \log nlogn
Step 2：计算每层额外空间
例如：函数参数 + 局部变量（通常常数）
Step 3：相乘
Space = depth × per-call space \text{Space} = \text{depth} \times \text{per-call space}Space=depth×per-call space
示例：快速排序（递归深度分析）
最坏情况：单支树 → 深度 n → 空间O ( n ) O(n)O(n)
平均情况：深度log n \log nlogn→ 空间O ( log n ) O(\log n)O(logn)
因此快速排序空间复杂度：
- 最坏：O ( n ) O(n)O(n)
- 平均：O ( log n ) O(\log n)O(logn)
示例：二分搜索
深度 =log n \log nlogn
每次常数空间 →O ( log n ) O(\log n)O(logn)
四、总结（可直接加入文档）
常见空间复杂度：
- O ( 1 ) O(1)O(1)：双指针、原地算法
- O ( log n ) O(\log n)O(logn)：二分、平衡树
- O ( n ) O(n)O(n)：DFS 栈、线性 DP
- O ( n 2 ) O(n^2)O(n2)：矩阵 DP
- O ( 2 n ) O(2^n)O(2n)/O ( n ! ) O(n!)O(n!)：回溯生成所有子集/排列
分析技巧：
循环法则（单层、嵌套、组合）
递归 = 深度 × 每帧空间
注意区分：
- 输入空间 vs 额外空间（Aux Space）
- 均摊空间（例如动态数组不涉及空间扩容开销分析）
五、标准库算法复杂度（C++ STL）
| 算法 / 操作 | 时间复杂度 | 空间复杂度（额外空间） | 说明 |
|---|---|---|---|
std::sort | O ( n log n ) O(n \log n)O(nlogn) | O ( log n ) O(\log n)O(logn) | 使用 introsort（快排 + 堆排 + 插入排序），递归深度为log n \log nlogn |
std::stable_sort | O ( n log n ) O(n \log n)O(nlogn) | O ( n ) O(n)O(n) | 归并排序实现，必须使用额外数组保证稳定性 |
std::partial_sort | O ( n log k ) O(n \log k)O(nlogk) | O ( log n ) O(\log n)O(logn) | 取前 k 小元素（堆 + 排序） |
std::nth_element | O ( n ) O(n)O(n)（期望） | O ( 1 ) O(1)O(1) | 快速选择（QuickSelect）原地进行 |
std::binary_search | O ( log n ) O(\log n)O(logn) | O ( 1 ) O(1)O(1) | 数组二分查找，不需额外空间 |
工程提示：
std::sort的空间复杂度非常低（接近原地），是工程上最常用排序。std::stable_sort若数据量巨大，会因线性额外空间消耗而不适用于嵌入式或内存敏感场景。
六、容器操作复杂度（C++ STL 容器）
以下为常见容器的典型操作复杂度 + 空间分析。
1.std::vector（动态数组）
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 随机访问 | O ( 1 ) O(1)O(1) | O ( 1 ) O(1)O(1) | 连续内存，支持数组式访问 |
| 尾部 push_back | O ( 1 ) O(1)O(1)（均摊） | 容量按倍增策略扩展 | |
| 尾部 pop_back | O ( 1 ) O(1)O(1) | — | 不复制元素 |
| 中间插入/删除 | O ( n ) O(n)O(n) | — | 需要 memmove 移动大量数据 |
| 扩容 | 摊还O ( 1 ) O(1)O(1)，单次最坏O ( n ) O(n)O(n) | 新容量通常为 2 倍 |
空间特点：
- capacity ≥ size
- 可能有额外未使用的内存（保留增长空间）
2.std::list（双向链表）
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 任意位置插入 | O ( 1 ) O(1)O(1) | 已知迭代器即可插入 |
| 任意位置删除 | O ( 1 ) O(1)O(1) | 不需要移动其它节点 |
| 随机访问 | O ( n ) O(n)O(n)) | 只能顺序遍历 |
| 查找某元素 | O ( n ) O(n)O(n)) | 不支持二分查找 |
空间特点：
- 每个节点独立分配，额外成本较高
- 强依赖指针（降低缓存友好性）
3.std::map/std::set（红黑树）
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O ( log n ) O(\log n)O(logn) | 平衡二叉树 |
| 插入 | O ( log n ) O(\log n)O(logn) | 需保持平衡 |
| 删除 | O ( log n ) O(\log n)O(logn) | — |
| 遍历 | O ( n ) O(n)O(n) | 中序遍历 |
空间特点：
- 每个节点分配内存 + 指针，结构复杂
- CPU 缓存局部性较差（相较于 vector）
4.unordered_map/unordered_set（哈希表）
| 操作 | 平均复杂度 | 最坏情况 | 说明 |
|---|---|---|---|
| 查找 | O ( 1 ) O(1)O(1) | O ( n ) O(n)O(n) | 哈希冲突大量堆积时退化 |
| 插入 | O ( 1 ) O(1)O(1) | O ( n ) O(n)O(n) | 可能 rehash |
| 删除 | O ( 1 ) O(1)O(1) | O ( n ) O(n)O(n) | — |
空间特点：
- 需要维护桶（bucket）数组
- 典型情况下 bucket 数量 ≈ 元素数量 → 空间常为O ( n ) O(n)O(n)
工程注意：
哈希表很快，但 rehash 代价（扩容）可能导致卡顿，实时系统要谨慎使用。
七、空间复杂度分析技巧（适用于所有算法）
技巧 1：循环结构空间分析
单层循环
额外空间一般为常数O ( 1 ) O(1)O(1)
嵌套循环
空间仍为O ( 1 ) O(1)O(1)，除非显式申请数组。
技巧 2：递归的空间复杂度
核心公式：
Space = max recursion depth × space per call \text{Space} = \text{max recursion depth} \times \text{space per call}Space=max recursion depth×space per call
常见递归深度
| 递归类型 | 深度 | 空间复杂度 |
|---|---|---|
| 二分 | log n \log nlogn | O ( log n ) O(\log n)O(logn) |
| 快速排序（平均） | log n \log nlogn | O ( log n ) O(\log n)O(logn) |
| 快速排序（最坏） | n nn | O ( n ) O(n)O(n) |
| DFS（链状图） | n nn | O ( n ) O(n)O(n) |
技巧 3：容器的空间分析
- 动态数组：size 与 capacity 分离
- 链表：每节点额外指针开销
- 哈希表：桶数组 + 元素链
- 平衡树：节点 + 多个指针
“空间复杂度 = 每个节点大小 × 节点数”
