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

复杂度分析是算法面试的第一道门。面试官不一定要求你把证明写得很严，但会希望你能说清：这段代码跑了多少轮、额外用了多少空间、输入规模变大后会发生什么。 先把一个边界讲清楚：复杂度分析通常看输入规模趋近很大时的增长趋势，不是精确运行时间。 不代表一定比 快，常数、数据规模、缓存命中和实现细节都会影响真实耗时。不过面试里先按 Big O 说清增长量级，再补一句实际场景的限制，就够用了。 面试考察重点 能根据循环、递归、数据结构操作判断时间复杂度。 能区分额外空间和输入本身占用的空间。 能说清最好、最坏、平均复杂度分别适合哪些算法。 遇到递归代码时，能用递归树或子问题规模分析。 不把 、排序、堆操作都默认当成 。 面试里怎么讲复杂度？ 回答复杂度时，不要只报一个结论。更好的说法是“代码做了什么，因此复杂度是多少”。 比如两数之和： 这个回答比单说 更稳，因为它把推导过程讲出来了。面试官如果继续追问哈希表最坏情况，也有接话空间。 常见复杂度量级 | 复杂度 | 常见场景 | 面试备注 | | | | | | | 数组按下标访问、栈顶操作、哈希表平均查询 | 哈希表最坏可能退化 | | | 二分查找、堆上浮/下沉、平衡树查询 | 每轮把规模缩小一部分 | | | 单次遍历数组、链表、字符串 | 看是否真的只扫一遍 | | | 快排平均、归并排序、堆排序 | 排序题最常见量级 | | | 双重循环、枚举两两组合 | 面试中要警惕是否能优化 | | | 子集枚举、部分回溯 | 子集枚举的搜索空间是指数级 | | | 全排列、旅行商暴力解 | 只适合小规模输入 | 一般来说，算法题输入规模会暗示可接受复杂度： | 输入规模 | 通常可接受的复杂度 | | | | | | 指数级、回溯、状态压缩 | | | 有时可以 | | | 常见 | | | 或 | | | 通常要接近 | 这不是硬规则，但能帮你在面试里判断暴力解是否可能超时。 循环复杂度怎么判断？ 普通循环看执行次数： 这段是 。 嵌套循环不能只看有几层，要看每层真实次数： 内层次数是 ，也就是 ，复杂度记作 。 如果循环变量每次翻倍，通常是 ： 还有一种容易误判的情况是双指针： 虽然是 里嵌了条件，但 和 都只单调递增，最多各移动 次，所以整体是 ，不是 。 递归复杂度怎么判断？ 递归复杂度可以先看两个问题： 1. 每层递归有多少个子问题？ 2. 每层除了递归调用，还做了多少额外工作？ 二分查找每次只进入一个子问题，规模减半： 递归深度是 ，每层只做 工作，所以时间复杂度是 ，递归栈空间是 。 归并排序每层拆成两个子问题，每层合并总工作量是 ，层数是 ，所以时间复杂度是 ，额外数组空间是 。 再看一个反例：普通递归斐波那契。 它不是 ，因为每次会继续拆成两个递归调用，很多子问题被重复计算，时间复杂度接近 。如果加记忆化数组，每个状态只算一次，时间复杂度就变成 ，空间复杂度也是 。 空间复杂度看什么？ 空间复杂度看算法运行过程中额外使用的空间，常见来源有： 新建数组、哈希表、队列、栈。 递归调用栈。 排序或合并时的辅助空间。 结果集是否算额外空间，要看题目要求。面试时可以主动说明。 比如反转链表的迭代写法只用了几个指针，空间复杂度是 。如果用递归反转，虽然没有显式创建数组，但递归栈深度是 ，空间复杂度是 。 常见易错点 排序不是免费的。先排序再双指针，时间复杂度通常至少是 。 查询平均是 ，但最坏情况不是。 递归没有显式创建集合，也可能有递归栈空间。 二维矩阵遍历通常是 ，不要顺手写成 。 BFS 的队列空间不是常数，最坏可能存下一层大量节点。 回溯题的复杂度经常和结果数量有关，不能只看递归深度。 高频问题自测 为什么复杂度分析通常忽略常数？ 一定比 快吗？ 快排的平均和最坏时间复杂度分别是多少？ 递归算法的空间复杂度怎么算？ DFS 和 BFS 的时间复杂度为什么通常是 ？ 哈希表查询为什么平均是 ？ 推荐练习题 704. 二分查找 912. 排序数组 206. 反转链表 200. 岛屿数量 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。