前言上一篇我们彻底讲清楚了时间复杂度。但算法面试、机试评分、代码优劣判断时间复杂度只占一半另一半就是空间复杂度。很多同学刷题只会分析时间一遇到空间、递归栈、递归复杂度直接翻车。本篇作为进阶续篇专门搞定- 空间复杂度怎么算- 什么是「原地算法」- 递归栈空间怎么统计- 递归时间复杂度通用推导方法- 面试高频坑点全覆盖全篇通俗、无废话、可直接背诵面试。一、什么是空间复杂度1.1 定义空间复杂度代码运行过程中额外开辟的存储空间随数据规模 n 的增长趋势。关键点1. 只算额外空间不算题目给的输入空间2. 和时间复杂度一样只看增长趋势舍弃常数、低阶3. 递归栈、数组、集合、临时变量全部计入空间开销1.2 为什么空间复杂度很重要1. 机试有内存限制很多题时间够但超内存MLE2. 面试高频提问是否为原地算法空间能否优化3. 大厂非常看重时间、空间双向最优二、空间复杂度三大等级精讲代码2.1 O(1) 常数空间最优原地算法不随 n 变化只使用固定少量变量常见交换变量、双指针遍历、基础运算def sum_n(n):res 0for i in range(n):res ireturn res仅开辟 res、i 两个变量和 n 无关 空间复杂度 O(1)满足 O(1) 的算法可称为 原地算法2.2 O(n) 线性空间随数据规模 n 开辟同等大小空间典型场景新建数组、List、哈希表def create_arr(n):arr [0] * nreturn arr数组长度随 n 线性增长 空间复杂度 O(n)2.3 O(n²) 平方空间二维数组、矩阵存储dp [[0]*n for _ in range(n)]n行n列总空间 $$n^2$$ 空间复杂度 O(n²)一般出现就属于高内存开销大题目基本会MLE。三、最容易被忽略的空间递归栈空间绝大多数新手失分点递归不创建数组也会占用空间3.1 递归栈规则- 每调用一次递归就会压入一层栈帧- 递归深度 栈空间复杂度案例1普通递归 O(n) 空间def dfs(n):if n 0:returndfs(n-1)递归深度n 层 空间复杂度 O(n)案例2二分递归 O(logn) 空间def binary(n):if n 0:returnbinary(n // 2)每次折半深度 logn 空间复杂度 O(logn)重点总结循环几乎不占额外空间递归一定吃栈空间四、递归时间复杂度通用推导面试核心循环复杂度肉眼可看递归必须公式推导4.1 递推公式法万能模板设 $$T(n)$$ 为 n 规模的时间复杂度1. 写出递推式2. 带入递归树 / 公式展开3. 取最高阶项例题1斐波那契递归def fib(n):if n 2:return 1return fib(n-1) fib(n-2)递推式$$T(n) T(n-1) T(n-2) O(1)$$递归树每层翻倍总节点数指数增长 时间复杂度 O(2ⁿ)例题2二分递归def find(n):if n 1:returnfind(n//2)递推式$$T(n) T(n/2) O(1)$$展开得$$logn$$ 层 时间复杂度 O(logn)例题3归并思想递归每层遍历 n 次一共 logn 层 时间复杂度 O(nlogn)五、面试6大高频坑点必背坑1只看数组不算递归栈很多人递归没数组 O(1)❌ 错递归深度就是空间坑2把输入数组算进空间复杂度题目给的参数、原始输入 不算额外空间坑3分不清原地算法O(1) 额外空间 原地O(logn) / O(n) 非原地坑4递归时间凭感觉猜递归不能肉眼看必须递推式递归树分析坑5忽略常数优化但卡死内存时间可以忽略常数空间常数开销很致命坑6DFS、回溯空间不会分析回溯算法本质递归空间取决于最大递归深度六、常见算法时空复杂度总表面试直接背- 冒泡/选择/插入排序$$O(n^2)$$、$$O(1)$$- 快速排序$$O(nlogn)$$、$$O(logn)$$栈深度- 归并排序$$O(nlogn)$$、$$O(n)$$- 二分查找$$O(logn)$$、$$O(1)$$- 普通遍历$$O(n)$$、$$O(1)$$- 斐波那契暴力递归$$O(2^n)$$、$$O(n)$$七、总结1. 空间复杂度统计额外开辟空间输入不算2. 变量固定不变O(1) 原地算法3. 递归空间看递归深度递归时间看递归树总节点4. 刷题必须双分析时间 空间5. 递归题是复杂度分析的最大难点也是面试拉分点---下期预告算法五大思维误区刷题一直没进步的根源补齐算法入门最后一块短板
前言上一篇我们彻底讲清楚了时间复杂度。但算法面试、机试评分、代码优劣判断时间复杂度只占一半另一半就是空间复杂度。很多同学刷题只会分析时间一遇到空间、递归栈、递归复杂度直接翻车。本篇作为进阶续篇专门搞定- 空间复杂度怎么算- 什么是「原地算法」- 递归栈空间怎么统计- 递归时间复杂度通用推导方法- 面试高频坑点全覆盖全篇通俗、无废话、可直接背诵面试。一、什么是空间复杂度1.1 定义空间复杂度代码运行过程中额外开辟的存储空间随数据规模 n 的增长趋势。关键点1. 只算额外空间不算题目给的输入空间2. 和时间复杂度一样只看增长趋势舍弃常数、低阶3. 递归栈、数组、集合、临时变量全部计入空间开销1.2 为什么空间复杂度很重要1. 机试有内存限制很多题时间够但超内存MLE2. 面试高频提问是否为原地算法空间能否优化3. 大厂非常看重时间、空间双向最优二、空间复杂度三大等级精讲代码2.1 O(1) 常数空间最优原地算法不随 n 变化只使用固定少量变量常见交换变量、双指针遍历、基础运算def sum_n(n):res 0for i in range(n):res ireturn res仅开辟 res、i 两个变量和 n 无关 空间复杂度 O(1)满足 O(1) 的算法可称为 原地算法2.2 O(n) 线性空间随数据规模 n 开辟同等大小空间典型场景新建数组、List、哈希表def create_arr(n):arr [0] * nreturn arr数组长度随 n 线性增长 空间复杂度 O(n)2.3 O(n²) 平方空间二维数组、矩阵存储dp [[0]*n for _ in range(n)]n行n列总空间 $$n^2$$ 空间复杂度 O(n²)一般出现就属于高内存开销大题目基本会MLE。三、最容易被忽略的空间递归栈空间绝大多数新手失分点递归不创建数组也会占用空间3.1 递归栈规则- 每调用一次递归就会压入一层栈帧- 递归深度 栈空间复杂度案例1普通递归 O(n) 空间def dfs(n):if n 0:returndfs(n-1)递归深度n 层 空间复杂度 O(n)案例2二分递归 O(logn) 空间def binary(n):if n 0:returnbinary(n // 2)每次折半深度 logn 空间复杂度 O(logn)重点总结循环几乎不占额外空间递归一定吃栈空间四、递归时间复杂度通用推导面试核心循环复杂度肉眼可看递归必须公式推导4.1 递推公式法万能模板设 $$T(n)$$ 为 n 规模的时间复杂度1. 写出递推式2. 带入递归树 / 公式展开3. 取最高阶项例题1斐波那契递归def fib(n):if n 2:return 1return fib(n-1) fib(n-2)递推式$$T(n) T(n-1) T(n-2) O(1)$$递归树每层翻倍总节点数指数增长 时间复杂度 O(2ⁿ)例题2二分递归def find(n):if n 1:returnfind(n//2)递推式$$T(n) T(n/2) O(1)$$展开得$$logn$$ 层 时间复杂度 O(logn)例题3归并思想递归每层遍历 n 次一共 logn 层 时间复杂度 O(nlogn)五、面试6大高频坑点必背坑1只看数组不算递归栈很多人递归没数组 O(1)❌ 错递归深度就是空间坑2把输入数组算进空间复杂度题目给的参数、原始输入 不算额外空间坑3分不清原地算法O(1) 额外空间 原地O(logn) / O(n) 非原地坑4递归时间凭感觉猜递归不能肉眼看必须递推式递归树分析坑5忽略常数优化但卡死内存时间可以忽略常数空间常数开销很致命坑6DFS、回溯空间不会分析回溯算法本质递归空间取决于最大递归深度六、常见算法时空复杂度总表面试直接背- 冒泡/选择/插入排序$$O(n^2)$$、$$O(1)$$- 快速排序$$O(nlogn)$$、$$O(logn)$$栈深度- 归并排序$$O(nlogn)$$、$$O(n)$$- 二分查找$$O(logn)$$、$$O(1)$$- 普通遍历$$O(n)$$、$$O(1)$$- 斐波那契暴力递归$$O(2^n)$$、$$O(n)$$七、总结1. 空间复杂度统计额外开辟空间输入不算2. 变量固定不变O(1) 原地算法3. 递归空间看递归深度递归时间看递归树总节点4. 刷题必须双分析时间 空间5. 递归题是复杂度分析的最大难点也是面试拉分点---下期预告算法五大思维误区刷题一直没进步的根源补齐算法入门最后一块短板
