介绍
空间复杂度（Space Complexity） 指算法在运行过程中占用了多少存储空间，指 额外开辟的辅助空间 随输入规模 n 增长的变化趋势，不包含输入、输出数据的原始存储空间，仅关注算法执行所需的 临时空间（如变量、数组、栈帧、动态分配内存等）。
反映算法对内存资源的消耗程度
如何计算算法的空间复杂度
在运行时使用的 辅助变量所占用的空间，即辅助空间，是衡量空间复杂度的关键因素
例子
将两个数交换
swap(int x,int y){ //x与y交换
int temp;
temp=x； //① temp 为辅助空间
x=y; //②
y=temp; //③
该算法使用了一个辅助空间（变量） temp，空间复杂度为 О(1)
例子2
注意：在 递归算法 中，每一次递推都需要一个 栈空间 来保存调用记录，因此计算空间复杂度时需要 计算递归栈的辅助空间。
long fac(int n){
if (n<0)
return -1;
else if(n==0 || n==1)
return 1;
else
return n*fac(n-1);
}
递归在系统内部使用栈实现，栈空间的大小为递归树的深度。计算 n 的阶乘，其递归树如下图所示：
计算 n 的阶乘时，递归树的深度为 n，因此递归算法的空间复杂度为 О(n)
计算规则
推导时只关注增长最快的项，忽略低阶项、常数系数、常数项，因为这些在输入规模 n 极大时，对内存占用的影响可以忽略：
忽略 常数项：开辟3个临时变量，空间复杂度为 O(1)（而非 O(3) ）；
忽略 常数系数：开辟 2n 个大小的数组，空间复杂度为O(n)（而非O(2n)）；
忽略 低阶项：开辟 n+5 个空间，复杂度为 O(n)（5是低阶常数项）；
关注 与输入规模 n 相关的空间：只有新开辟的空间数量随 n 变化时，才会影响复杂度等级。
常见算法的空间复杂度
| 算法 | 空间复杂度 | 备注 |
|---|---|---|
| 冒泡排序 | O(1) | 仅用临时变量交换，原地排序 |
| 快速排序 | O(log n)~O(n) | 递归栈空间，最优O(log n) |
| 归并排序 | O(n) | 需辅助数组合并数据 |
| 二分查找 | O(1)（迭代）/ O(log n)（递归） | 无额外辅助空间 |
| 哈希表查找 | O(n) | 需存储哈希表本身 |
重点案例解析
1. O(1) 常数空间（最常用）
算法执行中，仅开辟固定数量的临时变量/指针，无论输入规模 n 多大，额外空间都不变。
// 案例1：两数交换（仅用1个temp变量）
public static void swap(int[] arr, int i, int j) {
int temp = arr[i]; // 固定1个临时变量，与n无关
arr[i] = arr[j];
arr[j] = temp;
}
// 案例2：求数组和（仅用1个sum变量）
public static int getSum(int[] arr) {
int sum = 0; // 固定1个变量，无论arr多长，额外空间都不变
for (int num : arr) {
sum += num;
}
return sum;
}
结论：只要新开辟的空间数量是固定值，不管是1个还是100个，空间复杂度都是(O(1))。
2. O(n) 线性空间
算法执行中，开辟了与输入规模 n 成正比的新空间（比如新数组、新集合）。
// 案例：复制一个长度为n的数组（新开辟n个空间）
public static int[] copyArr(int[] arr) {
int n = arr.length;
int[] newArr = new int[n]; // 新数组长度= n，额外空间随n线性增长
for (int i = 0; i < n; i++) {
newArr[i] = arr[i];
}
return newArr;
}
结论：只要新开辟的空间数量等于n/2n/3n等，按规则忽略系数，复杂度都是(O(n))。
3. O(log n) 对数空间
额外空间随 n 增长但增长极慢，典型场景就是递归版算法的调用栈（比如你刚学的递归版快速排序）。
后续会结合快排详细讲，核心逻辑：每次把问题分成两半，递归深度为 \log_2 n，栈空间随递归深度增长。
空间复杂度 vs 时间复杂度
| 维度 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 衡量目标 | 算法执行的操作次数/耗时随n的变化 |
算法执行的临时空间占用随n的变化 |
| 核心关注点 | 运行速度 | 内存消耗 |
| 优化优先级 | 通常优先优化时间复杂度 | 内存受限场景下优先优化空间复杂度 |
权衡
实际开发中，算法的时间效率和空间效率往往是此消彼长的，这就是经典的时空权衡思想：
- 空间换时间：牺牲更多的空间，换取更快的运行速度（比如用哈希表存数据，把查找时间从(O(n))降到(O(1))）；
- 时间换空间：牺牲一点运行速度，换取更少的内存占用（比如为了节省空间，放弃哈希表，用线性查找）。
总结
- 空间复杂度描述的是额外辅助空间的增长趋势，而非绝对空间大小；
- 优先关注量级
（O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)），量级越小空间效率越高； - 实际开发中需时空权衡：有时用空间换时间（如缓存、哈希表），有时用时间换空间（如原地排序）。