时间复杂度和空间复杂度面试指南：Big O、递归复杂度与常见误区

Guide约 1763 字大约 6 分钟

复杂度分析是算法面试的第一道门。面试官不一定要求你把证明写得很严，但会希望你能说清：这段代码跑了多少轮、额外用了多少空间、输入规模变大后会发生什么。

先把一个边界讲清楚：复杂度分析通常看输入规模趋近很大时的增长趋势，不是精确运行时间。O(n) 不代表一定比 O(nlogn) 快，常数、数据规模、缓存命中和实现细节都会影响真实耗时。不过面试里先按 Big O 说清增长量级，再补一句实际场景的限制，就够用了。

面试考察重点

能根据循环、递归、数据结构操作判断时间复杂度。
能区分额外空间和输入本身占用的空间。
能说清最好、最坏、平均复杂度分别适合哪些算法。
遇到递归代码时，能用递归树或子问题规模分析。
不把 HashMap、排序、堆操作都默认当成 O(1)。

面试里怎么讲复杂度？

回答复杂度时，不要只报一个结论。更好的说法是“代码做了什么，因此复杂度是多少”。

比如两数之和：

数组遍历一遍，每个元素在 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)`

这不是硬规则，但能帮你在面试里判断暴力解是否可能超时。

循环复杂度怎么判断？

普通循环看执行次数：

for (int i = 0; i < n; i++) {
    // O(1)
}

这段是 O(n)。

嵌套循环不能只看有几层，要看每层真实次数：

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

for (int i = 1; i < n; i *= 2) {
    // O(1)
}

还有一种容易误判的情况是双指针：

while (left < n && right < n) {
    if (needMoveRight()) {
        right++;
    } else {
        left++;
    }
}

虽然是 while 里嵌了条件，但 left 和 right 都只单调递增，最多各移动 n 次，所以整体是 O(n)，不是 O(n^2)。

递归复杂度怎么判断？

递归复杂度可以先看两个问题：

每层递归有多少个子问题？
每层除了递归调用，还做了多少额外工作？

二分查找每次只进入一个子问题，规模减半：

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

再看一个反例：普通递归斐波那契。

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

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。