算法复杂度分析之——空间复杂度分析和标准库算法与容器操作的复杂度实际案例分析（3）

相关内容地址：算法复杂度分析 —形式化的均摊复杂度证明和 Master 定理示例（2）

一、常见空间复杂度（Space Complexity）

空间复杂度衡量算法额外占用的内存大小随输入规模 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!)：回溯生成所有子集/排列

分析技巧：

1. 循环法则（单层、嵌套、组合）

2. 递归 = 深度 × 每帧空间

3. 注意区分：

   • 输入空间 vs 额外空间（Aux Space）
   • 均摊空间（例如动态数组不涉及空间扩容开销分析）

五、标准库算法复杂度（C++ STL）

工程提示：

• std::sort的空间复杂度非常低（接近原地），是工程上最常用排序。
• std::stable_sort若数据量巨大，会因线性额外空间消耗而不适用于嵌入式或内存敏感场景。

六、容器操作复杂度（C++ STL 容器）

以下为常见容器的典型操作复杂度 + 空间分析。

1.std::vector（动态数组）

空间特点：

• capacity ≥ size
• 可能有额外未使用的内存（保留增长空间）

2.std::list（双向链表）

空间特点：

• 每个节点独立分配，额外成本较高
• 强依赖指针（降低缓存友好性）

3.std::map/std::set（红黑树）

空间特点：

• 每个节点分配内存 + 指针，结构复杂
• CPU 缓存局部性较差（相较于 vector）

4.unordered_map/unordered_set（哈希表）

空间特点：

• 需要维护桶（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

常见递归深度

技巧 3：容器的空间分析

• 动态数组：size 与 capacity 分离
• 链表：每节点额外指针开销
• 哈希表：桶数组 + 元素链
• 平衡树：节点 + 多个指针

“空间复杂度 = 每个节点大小 × 节点数”