算法复杂度：空间复杂度（衡量占用空间大小）-马育民老师

# 介绍

**空间复杂度（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` 的阶乘，其递归树如下图所示：

![](https://www.malaoshi.top/upload/0/0/1GW2hgjdd6w7.png)

计算 `n` 的阶乘时，递归树的深度为 `n`，因此递归算法的空间复杂度为 `О(n)`

# 计算规则

推导时只关注**增长最快的项**，忽略低阶项、常数系数、常数项，因为这些在输入规模 $$n$$ 极大时，对内存占用的影响可以忽略：

1. 忽略 **常数项**：开辟3个临时变量，空间复杂度为 $$O(1)$$（而非 $$O(3)$$ ）；

2. 忽略 **常数系数**：开辟 $$2n$$ 个大小的数组，空间复杂度为$$O(n)$$（而非$$O(2n)$$）；

3. 忽略 **低阶项**：开辟 $$n+5$$ 个空间，复杂度为 $$O(n)$$（5是低阶常数项）；

4. 关注 **与输入规模 $$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$$ 多大，额外空间都不变。

```java
// 案例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$$ 成正比的新空间**（比如新数组、新集合）。

```java
// 案例：复制一个长度为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`的变化 |
| 核心关注点   | 运行速度                          | 内存消耗                          |
| 优化优先级   | 通常优先优化时间复杂度            | 内存受限场景下优先优化空间复杂度  |

### 权衡

实际开发中，算法的**时间效率**和**空间效率**往往是**此消彼长**的，这就是经典的**时空权衡**思想：

1. **空间换时间**：牺牲更多的空间，换取更快的运行速度（比如用哈希表存数据，把查找时间从$O(n)$降到$O(1)$）；
2. **时间换空间**：牺牲一点运行速度，换取更少的内存占用（比如为了节省空间，放弃哈希表，用线性查找）。

# 总结

1. 空间复杂度描述的是**额外辅助空间**的增长趋势，而非绝对空间大小；
2. 优先关注量级 `（O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)）`，量级越小空间效率越高；
3. 实际开发中需**时空权衡**：有时用空间换时间（如缓存、哈希表），有时用时间换空间（如原地排序）。

原文出处：http://www.malaoshi.top/show_1GW2hPn5WEk0.html