空间复杂度衡量算法运行过程中额外占用的存储空间随问题规模 $n$ 的增长趋势。注意：只计算辅助空间，不包括输入数据本身占用的空间。
分析方法：① 分析声明的变量、数组、递归栈等额外空间；② 统计与 $n$ 的关系；③ 用大 O 写出 $S(n)$。
原地算法（In-place）：空间复杂度为 $O(1)$ 的算法，只需常数级额外空间。如冒泡排序、插入排序是原地算法；归并排序（需辅助数组）不是原地算法。
递归算法的空间复杂度需考虑递归调用栈的深度。递归深度为 $n$ 时，空间复杂度至少为 $O(n)$。
// 递归求阶乘：递归深度 = n，空间复杂度 O(n)
int fact(int n){
if(n<=1) return 1;
return n * fact(n-1); // 每层调用占用栈帧
}| 空间复杂度 | 含义 | 典型算法 |
|---|---|---|
| $O(1)$ | 常数级辅助空间（原地） | 冒泡、选择、插入排序 |
| $O(\log n)$ | 对数级辅助空间 | 快速排序（平均递归栈） |
| $O(n)$ | 线性级辅助空间 | 归并排序（辅助数组）、基数排序 |
| $O(n^2)$ | 平方级辅助空间 | 某些动态规划 |
| 考法 | 解题套路 |
|---|---|
| 求空间复杂度 | 统计辅助空间：数组大小 + 递归栈深度 |
| 是否原地 | 空间复杂度是否为 $O(1)$ |
| 递归算法 | 递归栈深度 = 递归调用最大层数 |
| 比较排序 | 冒泡/插入 $O(1)$，快排平均 $O(\log n)$，归并 $O(n)$ |
↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。