企业官网建设流程全解析

前言

上一篇我们彻底讲清楚了时间复杂度。

但算法面试、机试评分、代码优劣判断，时间复杂度只占一半，另一半就是空间复杂度。

很多同学刷题只会分析时间，一遇到空间、递归栈、递归复杂度直接翻车。

本篇作为进阶续篇，专门搞定：

- 空间复杂度怎么算

- 什么是「原地算法」

- 递归栈空间怎么统计

- 递归时间复杂度通用推导方法

- 面试高频坑点全覆盖

全篇通俗、无废话、可直接背诵面试。

一、什么是空间复杂度？

1.1 定义

空间复杂度：代码运行过程中，额外开辟的存储空间随数据规模 n 的增长趋势。

关键点：

1. 只算额外空间，不算题目给的输入空间

2. 和时间复杂度一样，只看增长趋势，舍弃常数、低阶

3. 递归栈、数组、集合、临时变量全部计入空间开销

1.2 为什么空间复杂度很重要？

1. 机试有内存限制，很多题时间够但超内存MLE

2. 面试高频提问：是否为原地算法？空间能否优化？

3. 大厂非常看重：时间、空间双向最优

二、空间复杂度三大等级（精讲+代码）

2.1 O(1) 常数空间（最优｜原地算法）

不随 n 变化，只使用固定少量变量

常见：交换变量、双指针遍历、基础运算

def sum_n(n):

res = 0

for i in range(n):

res += i

return res

仅开辟 res、i 两个变量，和 n 无关

👉 空间复杂度 O(1)

满足 O(1) 的算法，可称为 原地算法

2.2 O(n) 线性空间

随数据规模 n 开辟同等大小空间

典型场景：新建数组、List、哈希表

def create_arr(n):

arr = [0] * n

return 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:

return

dfs(n-1)

递归深度：n 层

👉 空间复杂度 O(n)

案例2：二分递归 O(logn) 空间

def binary(n):

if n == 0:

return

binary(n // 2)

每次折半，深度 logn

👉 空间复杂度 O(logn)

重点总结：

循环几乎不占额外空间，递归一定吃栈空间

四、递归时间复杂度通用推导（面试核心）

循环复杂度肉眼可看，递归必须公式推导

4.1 递推公式法（万能模板）

设 $$T(n)$$ 为 n 规模的时间复杂度

1. 写出递推式

2. 带入递归树 / 公式展开

3. 取最高阶项

例题1：斐波那契递归

def fib(n):

if n <= 2:

return 1

return 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:

return

find(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：忽略常数优化但卡死内存

时间可以忽略常数，空间常数开销很致命

坑6：DFS、回溯空间不会分析

回溯算法本质递归，空间取决于最大递归深度

六、常见算法时空复杂度总表（面试直接背）

- 冒泡/选择/插入排序：$$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. 递归题是复杂度分析的最大难点，也是面试拉分点

---

下期预告：算法五大思维误区（刷题一直没进步的根源），补齐算法入门最后一块短板！