3.空间复杂度
如果不考虑时间和空间的因素，所有的问题都可以通过穷举法解决。
这也是一开始做AI的强调算力的原因。
一，概念
空间复杂度是指算法在执行过程中所需要的存储空间。
包括算法运行时使用的变量/数组/链表 等数据结构所占用的内存空间。
通俗一点说，就是一个算法，内存用了多少（空间复杂度），执行了多长时间（时间复杂度）
所以，其实程序设计很简单，空间复杂度尽量低，时间复杂度尽量低。当然了，在没有bug的前提下。
以前的程序员，很在意这两个指标，是因为以前的计算机或者芯片存储有限，cpu性能弱，现在的计算机，存储大大的，性能过剩，所以，这两个指标弱一点也没关系。除非一些特殊的需求，例如某些ADC采集，要在尽量小的时间内将采样数据计算完毕。
二，常见数据结构的空间复杂度
下面是常见数据结构和算法操作的时间复杂度与空间复杂度对照表：
一、常见数据结构操作复杂度
数据结构 | 操作 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
数组 | 访问 | O(1) | O(1) | O(n) |
搜索 | O(n) | O(n) | ||
插入 | O(n) | O(n) | ||
删除 | O(n) | O(n) | ||
链表 | 访问 | O(n) | O(n) | O(n) |
搜索 | O(n) | O(n) | ||
插入（首尾） | O(1) | O(1) | ||
删除（首尾） | O(1) | O(1) | ||
栈 | 入栈 | O(1) | O(1) | O(n) |
出栈 | O(1) | O(1) | ||
访问栈顶 | O(1) | O(1) | ||
队列 | 入队 | O(1) | O(1) | O(n) |
出队 | O(1) | O(1) | ||
访问队首 | O(1) | O(1) | ||
哈希表 | 访问 | O(1) | O(n) | O(n) |
搜索 | O(1) | O(n) | ||
插入 | O(1) | O(n) | ||
删除 | O(1) | O(n) | ||
二叉搜索树 | 访问 | O(log n) | O(n) | O(n) |
搜索 | O(log n) | O(n) | ||
插入 | O(log n) | O(n) | ||
删除 | O(log n) | O(n) | ||
平衡二叉树 | 访问 | O(log n) | O(log n) | O(n) |
搜索 | O(log n) | O(log n) | ||
插入 | O(log n) | O(log n) | ||
删除 | O(log n) | O(log n) | ||
图（邻接表） | 访问顶点 | O(1) | O(1) | O(n+m) |
访问边 | O(1) | O(1) | ||
遍历（BFS/DFS） | O(n+m) | O(n+m) |
二、常见排序算法复杂度
排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 |
桶排序 | O(n + k) | O(n) | O(n²) | O(n + k) | 稳定 |
基数排序 | O(d * (n + k)) | O(d * (n + k)) | O(d * (n + k)) | O(n + k) | 稳定 |
注：
- n 为数据规模，k 为桶/基数的范围，d 为基数排序的位数。
- 空间复杂度 O(1) 表示原地排序，不占用额外辅助空间。
- 顺序表：O (n)，其中 n 是顺序表的长度。
- 链表：O (n)，其中 n 是链表的长度。
- 栈：O (n)，其中 n 是栈的最大深度。
- 队列：O (n)，其中 n 是队列的最大长度。
- 哈希表：O (n)，其中 n 是哈希表中元素的数量。
- 树：O (n)，其中 n 是树的结点数量。
- 图：O (n+m)，其中 n 是图中顶点的数量，m 是图中边的数量。
三、常见图算法复杂度
算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
深度优先搜索 (DFS) | O(n + m) | O(n) | 连通性、拓扑排序、强连通分量 |
广度优先搜索 (BFS) | O(n + m) | O(n) | 最短路径（无权图）、连通性 |
Dijkstra 算法 | O((n + m) log n) | O(n) | 单源最短路径（非负权图） |
Bellman-Ford 算法 | O(nm) | O(n) | 单源最短路径（可处理负权） |
Floyd-Warshall 算法 | O(n³) | O(n²) | 所有顶点对最短路径 |
Kruskal 算法 | O(m log m) | O(m) | 最小生成树（稀疏图） |
Prim 算法 | O((n + m) log n) | O(n) | 最小生成树（稠密图） |
三，空间换时间
通常使用额外空间的目的，就是为了换取时间上的效率，也就是我们常说的空间换时间。最经典的空间换时间就是动态规划，例如求一个斐波那契数列的第 n 项的值，如果不做任何优化，就是利用循环进行计算，时间复杂度 O (n)，但是如果引入了数组，将计算结果预先存储在数组中，那么每次询问只需要 O (1) 的时间复杂度就可以得到第 n 项的值，而这时，由于引入了数组，所以空间复杂度就变成了 O (n)。
空间换时间 vs 时间换空间 典型场景对照表
策略 | 核心思想 | 典型场景 | 时间复杂度变化 | 空间复杂度变化 | 适用场景 |
空间换时间 | 用额外的存储空间，来减少计算或查询的时间开销 | 1.动态规划：斐波那契数列、背包问题，用数组存储子问题解，避免重复计算。 | 通常降低（如从O(n)→O(1)或O(log n)） | 通常升高（如从O(1)→O(n)） | 对响应时间敏感、内存资源相对充足的场景，如Web服务、数据库索引、高频查询系统。 |
时间换空间 | 用更多的计算时间，来减少对存储空间的占用 | 1.原地排序：快速排序、堆排序，在原数组上排序，空间复杂度O(1)。 | 通常升高（如从O(1)→O(n)） | 通常降低（如从O(n)→O(1)） | 内存资源受限、对时间要求不苛刻的场景，如嵌入式设备、移动应用、处理超大规模数据集。 |
补充说明
- 空间换时间的本质是“预计算+存储”，通过牺牲内存来换取更快的响应速度。
- 时间换空间的本质是“按需计算+复用”，通过牺牲CPU时间来节省内存。
- 实际工程中，需要根据具体的性能瓶颈和资源约束来选择策略，而不是绝对地偏向某一种。