wehub-resource-sync
186 lines
7.2 KiB
Markdown
186 lines
7.2 KiB
Markdown
---
|
||
title: 时间复杂度和空间复杂度面试指南：Big O、递归复杂度与常见误区
|
||
description: 时间复杂度和空间复杂度面试指南，系统讲解 Big O、循环复杂度、递归复杂度、空间复杂度、输入规模判断和算法面试常见复杂度误区。
|
||
category: 计算机基础
|
||
tag:
|
||
- 算法
|
||
head:
|
||
- - meta
|
||
- name: keywords
|
||
content: 时间复杂度,空间复杂度,Big O,递归复杂度,循环复杂度,算法复杂度,复杂度分析,算法面试题,LeetCode复杂度
|
||
---
|
||
|
||
复杂度分析是算法面试的第一道门。面试官不一定要求你把证明写得很严，但会希望你能说清：这段代码跑了多少轮、额外用了多少空间、输入规模变大后会发生什么。
|
||
|
||
先把一个边界讲清楚：复杂度分析通常看输入规模趋近很大时的增长趋势，不是精确运行时间。`O(n)` 不代表一定比 `O(nlogn)` 快，常数、数据规模、缓存命中和实现细节都会影响真实耗时。不过面试里先按 Big O 说清增长量级，再补一句实际场景的限制，就够用了。
|
||
|
||
## 面试考察重点
|
||
|
||
- 能根据循环、递归、数据结构操作判断时间复杂度。
|
||
- 能区分额外空间和输入本身占用的空间。
|
||
- 能说清最好、最坏、平均复杂度分别适合哪些算法。
|
||
- 遇到递归代码时，能用递归树或子问题规模分析。
|
||
- 不把 `HashMap`、排序、堆操作都默认当成 `O(1)`。
|
||
|
||
## 面试里怎么讲复杂度？
|
||
|
||
回答复杂度时，不要只报一个结论。更好的说法是“代码做了什么，因此复杂度是多少”。
|
||
|
||
比如两数之和：
|
||
|
||
```text
|
||
数组遍历一遍，每个元素在 HashMap 中做一次查询和一次插入，哈希表操作平均 O(1)，所以时间复杂度是 O(n)。额外使用了一个 HashMap 存元素到下标的映射，最坏会存 n 个元素，所以空间复杂度是 O(n)。
|
||
```
|
||
|
||
这个回答比单说 `O(n)` 更稳，因为它把推导过程讲出来了。面试官如果继续追问哈希表最坏情况，也有接话空间。
|
||
|
||
## 常见复杂度量级
|
||
|
||
| 复杂度 | 常见场景 | 面试备注 |
|
||
| ---------- | ---------------------------------------- | -------------------------- |
|
||
| `O(1)` | 数组按下标访问、栈顶操作、哈希表平均查询 | 哈希表最坏可能退化 |
|
||
| `O(logn)` | 二分查找、堆上浮/下沉、平衡树查询 | 每轮把规模缩小一部分 |
|
||
| `O(n)` | 单次遍历数组、链表、字符串 | 看是否真的只扫一遍 |
|
||
| `O(nlogn)` | 快排平均、归并排序、堆排序 | 排序题最常见量级 |
|
||
| `O(n^2)` | 双重循环、枚举两两组合 | 面试中要警惕是否能优化 |
|
||
| `O(2^n)` | 子集枚举、部分回溯 | 子集枚举的搜索空间是指数级 |
|
||
| `O(n!)` | 全排列、旅行商暴力解 | 只适合小规模输入 |
|
||
|
||
一般来说，算法题输入规模会暗示可接受复杂度：
|
||
|
||
| 输入规模 | 通常可接受的复杂度 |
|
||
| ----------- | ---------------------- |
|
||
| `n <= 20` | 指数级、回溯、状态压缩 |
|
||
| `n <= 100` | `O(n^3)` 有时可以 |
|
||
| `n <= 1000` | `O(n^2)` 常见 |
|
||
| `n <= 10^5` | `O(nlogn)` 或 `O(n)` |
|
||
| `n >= 10^6` | 通常要接近 `O(n)` |
|
||
|
||
这不是硬规则，但能帮你在面试里判断暴力解是否可能超时。
|
||
|
||
## 循环复杂度怎么判断？
|
||
|
||
普通循环看执行次数：
|
||
|
||
```java
|
||
for (int i = 0; i < n; i++) {
|
||
// O(1)
|
||
}
|
||
```
|
||
|
||
这段是 `O(n)`。
|
||
|
||
嵌套循环不能只看有几层，要看每层真实次数：
|
||
|
||
```java
|
||
for (int i = 0; i < n; i++) {
|
||
for (int j = i; j < n; j++) {
|
||
// O(1)
|
||
}
|
||
}
|
||
```
|
||
|
||
内层次数是 `n + (n - 1) + ... + 1`，也就是 `n(n + 1) / 2`，复杂度记作 `O(n^2)`。
|
||
|
||
如果循环变量每次翻倍，通常是 `O(logn)`：
|
||
|
||
```java
|
||
for (int i = 1; i < n; i *= 2) {
|
||
// O(1)
|
||
}
|
||
```
|
||
|
||
还有一种容易误判的情况是双指针：
|
||
|
||
```java
|
||
while (left < n && right < n) {
|
||
if (needMoveRight()) {
|
||
right++;
|
||
} else {
|
||
left++;
|
||
}
|
||
}
|
||
```
|
||
|
||
虽然是 `while` 里嵌了条件，但 `left` 和 `right` 都只单调递增，最多各移动 `n` 次，所以整体是 `O(n)`，不是 `O(n^2)`。
|
||
|
||
## 递归复杂度怎么判断？
|
||
|
||
递归复杂度可以先看两个问题：
|
||
|
||
1. 每层递归有多少个子问题？
|
||
2. 每层除了递归调用，还做了多少额外工作？
|
||
|
||
二分查找每次只进入一个子问题，规模减半：
|
||
|
||
```java
|
||
int binarySearch(int[] nums, int target, int left, int right) {
|
||
if (left > right) {
|
||
return -1;
|
||
}
|
||
int mid = left + (right - left) / 2;
|
||
if (nums[mid] == target) {
|
||
return mid;
|
||
}
|
||
if (nums[mid] < target) {
|
||
return binarySearch(nums, target, mid + 1, right);
|
||
}
|
||
return binarySearch(nums, target, left, mid - 1);
|
||
}
|
||
```
|
||
|
||
递归深度是 `logn`，每层只做 `O(1)` 工作，所以时间复杂度是 `O(logn)`，递归栈空间是 `O(logn)`。
|
||
|
||
归并排序每层拆成两个子问题，每层合并总工作量是 `O(n)`，层数是 `logn`，所以时间复杂度是 `O(nlogn)`，额外数组空间是 `O(n)`。
|
||
|
||
再看一个反例：普通递归斐波那契。
|
||
|
||
```java
|
||
int fib(int n) {
|
||
if (n <= 1) {
|
||
return n;
|
||
}
|
||
return fib(n - 1) + fib(n - 2);
|
||
}
|
||
```
|
||
|
||
它不是 `O(n)`，因为每次会继续拆成两个递归调用，很多子问题被重复计算，时间复杂度接近 `O(2^n)`。如果加记忆化数组，每个状态只算一次，时间复杂度就变成 `O(n)`，空间复杂度也是 `O(n)`。
|
||
|
||
## 空间复杂度看什么？
|
||
|
||
空间复杂度看算法运行过程中额外使用的空间，常见来源有：
|
||
|
||
- 新建数组、哈希表、队列、栈。
|
||
- 递归调用栈。
|
||
- 排序或合并时的辅助空间。
|
||
- 结果集是否算额外空间，要看题目要求。面试时可以主动说明。
|
||
|
||
比如反转链表的迭代写法只用了几个指针，空间复杂度是 `O(1)`。如果用递归反转，虽然没有显式创建数组，但递归栈深度是 `n`，空间复杂度是 `O(n)`。
|
||
|
||
## 常见易错点
|
||
|
||
- 排序不是免费的。先排序再双指针，时间复杂度通常至少是 `O(nlogn)`。
|
||
- `HashMap` 查询平均是 `O(1)`，但最坏情况不是。
|
||
- 递归没有显式创建集合，也可能有递归栈空间。
|
||
- 二维矩阵遍历通常是 `O(mn)`，不要顺手写成 `O(n)`。
|
||
- BFS 的队列空间不是常数，最坏可能存下一层大量节点。
|
||
- 回溯题的复杂度经常和结果数量有关，不能只看递归深度。
|
||
|
||
## 高频问题自测
|
||
|
||
- 为什么复杂度分析通常忽略常数？
|
||
- `O(n)` 一定比 `O(nlogn)` 快吗？
|
||
- 快排的平均和最坏时间复杂度分别是多少？
|
||
- 递归算法的空间复杂度怎么算？
|
||
- DFS 和 BFS 的时间复杂度为什么通常是 `O(V + E)`？
|
||
- 哈希表查询为什么平均是 `O(1)`？
|
||
|
||
## 推荐练习题
|
||
|
||
- [704. 二分查找](https://leetcode.cn/problems/binary-search/)
|
||
- [912. 排序数组](https://leetcode.cn/problems/sort-an-array/)
|
||
- [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)
|
||
- [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)
|
||
|
||
<!-- @include: @article-footer.snippet.md -->
|