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