3.空间复杂度
如果不考虑时间和空间的因素，所有的问题都可以通过穷举法解决。这也是一开始做AI的强调算力的原因。
如果不考虑时间和空间的因素，所有的问题都可以通过穷举法解决。
这也是一开始做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时间来节省内存。
- 实际工程中，需要根据具体的性能瓶颈和资源约束来选择策略，而不是绝对地偏向某一种。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
8
0- 0
已为社区贡献3条内容
所有评论(0)