空间复杂度 O(n) 算法执行过程中额外申请的存储空间不包括输入数据空间优化技术从空间复杂度的角度进行空间优化时顾名思义就是让空间复杂度不复杂思路就是极简不额外申请不留的销毁/释放只留当前所需不得不留的压缩。什么是空间复杂度数组arr 有 1 亿个元素都叫total。那么数组的空间复杂度O(1)。因为不管 arr 有 1 个元素还是 1 亿个total 就一个变量。for x in arr: total x return total # 空间复杂度 O(1)不管 arr 多大total 始终一个变量包含一亿个 int的 数组空间复杂度算法层面O(1)没开新数组数组本身占用内存1 亿 × 4 字节 400 MB跟算法无关实际占的物理空间叫footprint不等于空间复杂度。又开个等长数组呢空间复杂度变成O(1亿)了因为额外开了个和输入一样大的数组。def copy(arr): return [x for x in arr] # 空间复杂度 O(n)额外开了一个等长数组算法的空间复杂度O(n)就是给这个算法额外申请多大空间快速排序的空间复杂度O(log n)—— arr 是输入不算递归栈是额外开的算。随着递归分区栈层数加深后进先出弹出后栈帧销毁递归栈呆着的内存空间是额外申请的。def quicksort(arr): quicksort_helper(arr, 0, len(arr)-1) # 递归栈给这个递归栈申请多大空间呢上面知道数组的空间复杂度是O(1)分区1次栈层数1平均情况下O(log n)层那么快速排序需要的临时空间——平均空间复杂度就是O(log n)。最坏空间复杂度是O(n²。数据实际占的空间有没有用有用但它在另一个层面叫内存占用 / footprint不叫空间复杂度。工程上关心的几个真实指标指标含义例子字面量空间数据结构实际占的字节struct Node { int val; Node* next; }占 16 字节空间复杂度算法额外开的空间递归栈、临时数组驻留集RSS进程实际占的物理内存看top命令对象头开销每个对象的元数据Java开销小Python开销大整个算法占用的空间≈数据结构实际占的字节算法额外开的空间进程实际占的物理内存每个对象的元数据常见算法 / 数据结构复杂度速查表1、基础数据结构数据结构 / 操作时间平均时间最坏空间适用场景数组按下标访问O(1)O(1)O(n)随机访问顺序查找O(n)O(n)O(1)无序线性查找二分查找O(log n)O(log n)O(1)有序数组冒泡 / 选择 / 插入排序O(n²)O(n²)O(1)小数据、教学归并排序O(n log n)O(n log n)O(n)稳定排序、大数据快速排序O(n log n)O(n²)O(log n)通用排序首选堆排序O(n log n)O(n log n)O(1)原地排序、Top K哈希表查找O(1)O(n)O(n)键值映射BST二叉搜索树O(log n)O(n)O(n)有序数据AVL / 红黑树O(log n)O(log n)O(n)平衡有序B 树 / B 树O(log n)O(log n)O(n)磁盘存储、数据库索引跳表O(log n)O(n)O(n)有序集合、RedisTrie前缀树O(m)O(m)O(Σ·m)字符串前缀、自动补全并查集路径压缩O(α(n)) ≈ O(1)O(log n)O(n)连通性问题2、按问题选数据结构的决策树速记同一个问题不同数据结构空间差很多存 1000 个点、10000 条边的图邻接表O(VE) 1.1 万邻接矩阵O(V²) 100 万差了将近 100 倍所以稀疏图千万别用邻接矩阵。需求选查第 K 大 / 动态 Top K堆范围求和 单点修改树状数组 / 线段树前缀匹配Trie连通性判断并查集最短路Dijkstra / SPFA字符串匹配KMP / Z 算法区间最值ST 表 / 线段树缓存 / 键值查找哈希表 LRU充分理解空间复杂度有什么用可以从空间复杂度角度进行空间优化。空间优化思路是极简不浪费不额外申请不留的销毁/释放只留当前所需不得不留的压缩。常用的空间优化技术有滚动数组在动态规划中只保留当前计算所需的前几行/列数据而非整个二维表格将空间从 O(n²) 降至 O(n)。状态压缩用位运算等技巧将多维状态压缩到一维或将状态用整数表示减少存储开销。推导式 / 递推数据边用边销毁不保留中间完整副本例如流式处理或迭代计算。局部变量作用域及时释放临时变量避免不必要的长生命周期占用内存。原地算法直接在输入数据上修改不额外申请等规模存储空间。数据分块 / 懒加载只加载当前需要处理的数据块而非一次性载入全部数据。fivebliss
