LeetCode-Book 图解空间复杂度从暂存空间、栈帧空间到时空权衡的完整实战指南【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《图解算法数据结构》专栏的「空间复杂度」章节leetbook_ioa/docs/# 1.4 空间复杂度.md系统讲解空间复杂度的空间类型划分、最差情况符号表示、五大常见数量级以及「空间换时间」的工程权衡并结合仓库内的 Python / Java / C 三语题解源码逐一验证结论。读完本文你将掌握空间复杂度的严谨分析方法能够独立推导递归栈帧空间的累计方式并在面试与刷题中正确对比不同解法的空间开销。一、空间复杂度衡量的究竟是什么1.1 算法复杂度的两个维度在进入空间复杂度之前先回顾《算法复杂度》中的定义算法复杂度旨在计算输入数据量为 $N$ 时算法的「时间使用」和「空间使用」情况体现算法运行所消耗资源随数据大小 $N$ 增大的速度。其中时间维度假设各操作的运行时间为固定常数统计算法运行的「计算操作数量」以此代表运行所需时间空间维度统计最差情况下算法运行所需使用的「最大空间」。「输入数据大小 $N$」在不同算法中有不同定义排序算法中 $N$ 代表待排序元素数量搜索算法中 $N$ 代表搜索范围的元素总数例如数组大小、矩阵大小、二叉树节点数、图节点和边数等。理解这一约定是正确计算空间复杂度的前提。1.2 空间复杂度的三类空间空间复杂度涉及的空间类型共有三种输入空间存储输入数据所需的空间大小暂存空间算法运行过程中存储所有中间变量和对象等数据所需的空间大小输出空间算法运行返回时存储输出数据所需的空间大小。通常情况下空间复杂度指在输入数据大小为 $N$ 时算法运行所使用的「暂存空间」「输出空间」的总体大小。在 LeetCode 刷题场景中有一个重要约定题目中的「输入空间」和「输出空间」往往是固定的、必须使用的内存空间例如传入的数组、要求返回的结果数组。因此本 LeetBook 的题目解析在统计空间复杂度时只统计「暂存空间」大小以便聚焦于算法本身的额外开销对比。这也是面试中分析复杂度时最常见的口径。二、内存空间的三个来源根据来源不同算法使用的内存空间分为三类指令空间、数据空间、栈帧空间。2.1 指令空间编译后程序指令所使用的内存空间。这部分空间由代码编译产物决定通常不随输入数据大小 $N$ 变化因此分析空间复杂度时一般不计入。2.2 数据空间算法中的各项变量使用的空间包括声明的常量、变量、动态数组、动态对象等。下面的三语示例展示了最典型的三种数据class Node: def __init__(self, val): self.val val self.next None def algorithm(N): num N # 变量 nums [0] * N # 动态数组 node Node(N) # 动态对象class Node { int val; Node next; Node(int x) { val x; } } void algorithm(int N) { int num N; // 变量 int[] nums new int[N]; // 动态数组 Node node new Node(N); // 动态对象 }struct Node { int val; Node *next; Node(int x) : val(x), next(NULL) {} }; void algorithm(int N) { int num N; // 变量 int nums[N]; // 动态数组 Node* node new Node(N); // 动态对象 }三者中变量num只占常数空间动态数组nums与N线性相关占 $O(N)$ 空间动态对象node则取决于对象内部成员的数量级。2.3 栈帧空间程序调用函数是基于栈实现的函数在调用期间占用常量大小的栈帧空间直至返回后释放。栈帧空间的关键在于理解「累计」与「释放」的时机情形一循环调用随调随释空间 $O(1)$如下代码在循环中调用test()每轮调用返回后栈帧空间立即释放因此任意时刻栈上至多只有一个test()的栈帧空间复杂度仍为 $O(1)$def test(): return 0 def algorithm(N): for _ in range(N): test()int test() { return 0; } void algorithm(int N) { for (int i 0; i N; i) { test(); } }int test() { return 0; } void algorithm(int N) { for (int i 0; i N; i) { test(); } }情形二递归调用层层累计空间 $O(N)$栈帧空间的累计常出现于递归调用。下面的递归函数在返回前会继续调用自身导致同时存在 $N$ 个未返回的algorithm()函数栈上累计 $O(N)$ 大小的栈帧空间def algorithm(N): if N 1: return 1 return algorithm(N - 1) 1int algorithm(int N) { if (N 1) return 1; return algorithm(N - 1) 1; }int algorithm(int N) { if (N 1) return 1; return algorithm(N - 1) 1; }从源码结构可以验证这一规律例如 LCR 123. 图书整理 I 题解 中方法一使用递归倒序输出链表其复杂度分析明确指出「系统递归需要使用 $O(N)$ 的栈空间」而方法二改用显式辅助栈后同样需要 $O(N)$ 额外空间存放节点值。递归的栈帧累计是空间复杂度分析中最容易被忽视、也最常考的点。三、符号表示以「最差情况」为准空间复杂度统计算法在**「最差情况」**下使用的空间大小以体现算法运行所需预留的空间量使用符号 $O$ 表示。最差情况有两层含义分别是「最差输入数据」与算法运行中的「最差运行点」。以下面的代码为例输入整数 $N$取值范围 $N \geq 1$def algorithm(N): num 5 # O(1) nums [0] * 10 # O(1) if N 10: nums [0] * N # O(N)void algorithm(int N) { int num 5; // O(1) int[] nums new int[10]; // O(1) if (N 10) { nums new int[N]; // O(N) } }void algorithm(int N) { int num 5; // O(1) vectorint nums(10); // O(1) if (N 10) { nums.resize(N); // O(N) } }最差输入数据当 $N \leq 10$ 时数组nums的长度恒定为 10空间复杂度为 $O(10) O(1)$当 $N 10$ 时数组nums长度为 $N$空间复杂度为 $O(N)$。因此空间复杂度取最差输入数据情况下的 $O(N)$。最差运行点执行nums [0] * 10时算法仅使用 $O(1)$ 空间而执行nums [0] * N时算法使用 $O(N)$ 空间。因此空间复杂度取最差运行点的 $O(N)$。这两层含义共同说明了一个结论空间复杂度关心的是算法在整个执行过程中可能达到的「空间峰值」而不是平均使用量。四、常见种类五大数量级逐一拆解根据从小到大排列常见的空间复杂度为$$ O(1) O(\log N) O(N) O(N^2) O(2^N) $$以下示例统一设输入数据大小为正整数 $N$并复用前面定义的节点类Node与函数test()。为保持三语言一致性节点类与函数定义如下# 节点类 Node class Node: def __init__(self, val): self.val val self.next None # 函数 test() def test(): return 0// 节点类 Node class Node { int val; Node next; Node(int x) { val x; } } // 函数 test() int test() { return 0; }// 节点类 Node struct Node { int val; Node *next; Node(int x) : val(x), next(NULL) {} }; // 函数 test() int test() { return 0; }4.1 常数 $O(1)$普通常量、变量、对象、元素数量与输入数据大小 $N$ 无关的集合皆使用常数大小的空间。即使集合规模很大如下方固定 10000 长度的数组只要不随 $N$ 变化仍属 $O(1)$def algorithm(N): num 0 nums [0] * 10000 node Node(0) dic { 0: 0 }void algorithm(int N) { int num 0; int[] nums new int[10000]; Node node new Node(0); MapInteger, String dic new HashMap() {{ put(0, 0); }}; }void algorithm(int N) { int num 0; int nums[10000]; Node* node new Node(0); unordered_mapint, string dic; dic.emplace(0, 0); }同样虽然函数test()被调用了 $N$ 次但每轮调用后即返回、无累计栈帧空间因此空间复杂度仍为 $O(1)$def algorithm(N): for _ in range(N): test()void algorithm(int N) { for (int i 0; i N; i) { test(); } }void algorithm(int N) { for (int i 0; i N; i) { test(); } }仓库实例在 LCR 126. 斐波那契数题解 中若新建长度为 $n$ 的dp列表空间复杂度为 $O(N)$由于dp[i]只与dp[i-1]、dp[i-2]有关可将列表优化为三个整型变量sum、a、b交替前进空间复杂度降至 $O(1)$。对应源码可见 selected_coding_interview/codes/python/lc_509_fibonacci_number.pyclass Solution: def fib(self, n: int) - int: a, b 0, 1 for _ in range(n): a, b b, a b return a同样LCR 141. 训练计划 III 题解反转链表的迭代双指针法中仅使用pre、cur、tmp三个指针变量遍历链表空间复杂度为 $O(1)$而同一题的递归实现因递归深度达到 $N$空间复杂度升至 $O(N)$ —— 这正是「同一问题、不同写法、不同空间开销」的典型对照。4.2 线性 $O(N)$元素数量与 $N$ 呈线性关系的任意类型集合常见于一维数组、链表、哈希表等皆使用线性大小的空间def algorithm(N): nums_1 [0] * N nums_2 [0] * (N // 2) nodes [Node(i) for i in range(N)] dic {} for i in range(N): dic[i] str(i)void algorithm(int N) { int[] nums_1 new int[N]; int[] nums_2 new int[N / 2]; ListNode nodes new ArrayList(); for (int i 0; i N; i) { nodes.add(new Node(i)); } MapInteger, String dic new HashMap(); for (int i 0; i N; i) { dic.put(i, String.valueOf(i)); } }void algorithm(int N) { int nums_1[N]; int nums_2[N / 2 1]; vectorNode* nodes; for (int i 0; i N; i) { nodes.push_back(new Node(i)); } unordered_mapint, string dic; for (int i 0; i N; i) { dic.emplace(i, to_string(i)); } }注意长度为 $N/2$ 的数组、含 $N$ 个元素的链表与哈希表其空间量级均为 $O(N)$常数系数不影响渐进复杂度。线性阶也常见于递归栈帧的累计——递归调用期间同时存在 $N$ 个未返回的algorithm()函数使用 $O(N)$ 大小的栈帧空间def algorithm(N): if N 1: return 1 return algorithm(N - 1) 1int algorithm(int N) { if (N 1) return 1; return algorithm(N - 1) 1; }int algorithm(int N) { if (N 1) return 1; return algorithm(N - 1) 1; }仓库实例LCR 123. 图书整理 I 题解 的辅助栈法中辅助栈stack与结果数组res合计使用 $O(N)$ 额外空间LCR 182. 动态口令题解 的字符串切片法中两个切片的长度总和为 $N$空间复杂度为 $O(N)$而该题 C 的「三次翻转法」因在原字符串上原地操作空间复杂度可降至 $O(1)$——同一题目在不同语言约束下呈现出截然不同的空间表现。4.3 平方 $O(N^2)$元素数量与 $N$ 呈平方关系的任意类型集合常见于矩阵皆使用平方大小的空间def algorithm(N): num_matrix [[0 for j in range(N)] for i in range(N)] node_matrix [[Node(j) for j in range(N)] for i in range(N)]void algorithm(int N) { int num_matrix[][] new int[N][N]; ListListNode node_matrix new ArrayList(); for (int i 0; i N; i) { ListNode nodes new ArrayList(); for (int j 0; j N; j) { nodes.add(new Node(j)); } node_matrix.add(nodes); } }void algorithm(int N) { vectorvectorint num_matrix; for (int i 0; i N; i) { vectorint nums; for (int j 0; j N; j) { nums.push_back(0); } num_matrix.push_back(nums); } vectorvectorNode* node_matrix; for (int i 0; i N; i) { vectorNode* nodes; for (int j 0; j N; j) { nodes.push_back(new Node(j)); } node_matrix.push_back(nodes); } }平方阶同样可以由「递归栈帧 每层数组」叠加而成下面的递归中同时存在 $N$ 个未返回的algorithm()函数使用 $O(N)$ 栈帧空间每层递归函数中声明了数组平均长度为 $\frac{N}{2}$使用 $O(N)$ 空间两者相乘总体空间复杂度为 $O(N^2)$def algorithm(N): if N 0: return 0 nums [0] * N return algorithm(N - 1)int algorithm(int N) { if (N 0) return 0; int[] nums new int[N]; return algorithm(N - 1); }int algorithm(int N) { if (N 0) return 0; int nums[N]; return algorithm(N - 1); }仓库实例LCR 130. 衣橱整理题解 中最差情况下 Set/矩阵visited存储矩阵所有单元格索引空间复杂度为 $O(MN)$LCR 157. 套餐内商品的排列顺序题解 中全排列递归深度为 $N$栈空间 $O(N)$而各层递归中辅助 Set 累计存储的字符数量最多为 $N (N-1) \cdots 1 (N1)N/2$即 $O(N^2)$ 额外空间——这是「递归栈 层内数据结构」共同构成平方阶空间的经典案例。4.4 指数 $O(2^N)$指数阶常见于二叉树、多叉树。例如高度为 $N$ 的「满二叉树」的节点数量为 $2^N$占用 $O(2^N)$ 大小的空间同理高度为 $N$ 的「满 $m$ 叉树」的节点数量为 $m^N$占用 $O(m^N) O(2^N)$ 大小的空间。指数阶空间增长极快一旦 $N$ 稍大内存即可能耗尽因此在设计中应极力避免。4.5 对数 $O(\log N)$对数阶常出现于分治算法的栈帧空间累计、数据类型转换等场景典型例子有两个快速排序平均空间复杂度为 $\Theta(\log N)$最差空间复杂度为 $O(N)$。拓展知识通过应用尾递归优化可以将快速排序的最差空间复杂度限定至 $O(N)$。数字转化为字符串设某正整数为 $N$其位数为 $\log_{10} N$即转化后的字符串长度为 $\log_{10} N$因此空间复杂度为 $O(\log N)$。仓库实例LCR 163. 找到第 k 位数字题解 中第三步将数字num转化为字符串str(num)占用 $O(\log k)$ 的额外空间正是「数字转字符串 → 空间 $O(\log N)$」的直接体现LCR 159. 库存管理 III 题解 方法二的「快速选择」利用哨兵划分只递归一侧子数组平均递归深度为 $O(\log N)$空间复杂度为 $O(\log N)$。五、时空权衡空间换时间与时间换空间对于算法的性能需要从时间和空间两个维度综合评价。优良的算法应具备两个特性时间复杂度和空间复杂度皆较低。而实际上同时优化两者非常困难——降低时间复杂度往往以提升空间复杂度为代价反之亦然。由于当代计算机的内存充足算法设计中通常采取「空间换时间」的做法即牺牲部分存储空间来提升算法的运行速度。以 LeetCode 全站第一题「两数之和」为例暴力枚举与辅助哈希表分别是「空间最优」和「时间最优」的两种算法。5.1 方法一暴力枚举时间换空间时间复杂度 $O(N^2)$空间复杂度 $O(1)$。该做法仅使用常数大小的额外空间但两层循环遍历所有数对运行速度过慢class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: for i in range(len(nums) - 1): for j in range(i 1, len(nums)): if nums[i] nums[j] target: return i, j returnclass Solution { public int[] twoSum(int[] nums, int target) { int size nums.length; for (int i 0; i size - 1; i) { for (int j i 1; j size; j) { if (nums[i] nums[j] target) return new int[] { i, j }; } } return new int[0]; } }class Solution { public: vectorint twoSum(vectorint nums, int target) { int size nums.size(); for (int i 0; i size - 1; i) { for (int j i 1; j size; j) { if (nums[i] nums[j] target) return { i, j }; } } return {}; } };5.2 方法二辅助哈希表空间换时间时间复杂度 $O(N)$空间复杂度 $O(N)$。借助辅助哈希表dic通过保存数组元素值与索引的映射在一次遍历中完成查找是本题的最佳解法class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: dic {} for i in range(len(nums)): if target - nums[i] in dic: return dic[target - nums[i]], i dic[nums[i]] i return []class Solution { public int[] twoSum(int[] nums, int target) { int size nums.length; MapInteger, Integer dic new HashMap(); for (int i 0; i size; i) { if (dic.containsKey(target - nums[i])) { return new int[] { dic.get(target - nums[i]), i }; } dic.put(nums[i], i); } return new int[0]; } }class Solution { public: vectorint twoSum(vectorint nums, int target) { int size nums.size(); unordered_mapint, int dic; for (int i 0; i size; i) { if (dic.find(target - nums[i]) ! dic.end()) { return { dic[target - nums[i]], i }; } dic.emplace(nums[i], i); } return {}; } };两种方案形成鲜明对比暴力枚举以 $O(N^2)$ 时间换 $O(1)$ 空间哈希表以 $O(N)$ 空间换 $O(N)$ 时间。在内存充足、时间受限的现代面试环境下「空间换时间」通常是更受青睐的选择。仓库中的同类权衡俯拾皆是LCR 123. 图书整理 I 的递归与辅助栈两法均为 $O(N)$ 空间LCR 141. 训练计划 III 中迭代法 $O(1)$ 空间 vs 递归法 $O(N)$ 空间LCR 159. 库存管理 III 中快速排序 $O(N)$ 空间 vs 快速选择 $O(\log N)$ 空间——每次「多开一份空间」往往都能换回更优的时间开销。六、示例题目速查按空间复杂度归类刷题在 LeetCode 题目中「输入空间」和「输出空间」往往是固定的、必须使用的内存空间。因希望专注于算法性能对比本 LeetBook 的题目解析的空间复杂度仅统计「暂存空间」大小。以下是各空间复杂度对应的仓库内示例题解便于对照学习空间复杂度示例题解$O(1)$LCR 126. 斐波那契数、LCR 141. 训练计划 III$O(\log N)$LCR 159. 库存管理 III、LCR 163. 找到第 k 位数字$O(N)$LCR 123. 图书整理 I、LCR 182. 动态口令$O(N^2)$LCR 130. 衣橱整理、LCR 157. 套餐内商品的排列顺序结合仓库内对应题解中的「复杂度分析」小节逐题验证是掌握空间复杂度分析最有效的路径——每个结论都能在 leetbook_ioa/docs/ 目录下找到完整的三语言推导与代码佐证。七、总结与自检清单空间复杂度分析可以归纳为三步分清空间类型只关注暂存空间 输出空间输入空间一般固定不计按指令空间、数据空间、栈帧空间三类来源逐一排查。锁定最差情况同时考虑最差输入数据与最差运行点取空间峰值使用 $O$ 符号表示。识别数量级数据集合看元素数量与 $N$ 的关系$O(1)$、$O(N)$、$O(N^2)$、$O(2^N)$、$O(\log N)$递归看「同时未返回的栈帧数 × 每层额外数据结构」的乘积。刷题自检时建议回答三个问题这段代码额外开了多大容器递归深度有多深、栈帧是否累计是否能用 $O(1)$ 的迭代替代 $O(N)$ 的递归反之亦然掌握这些判断你就能在面试中准确解释每一份代码的空间开销并在「空间换时间」与「时间换空间」之间做出合理决策。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考