02.1.1.1 时间空间复杂度与大 O
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架 / 02.1.1 复杂度与解题框架
02.1.1.1-001 什么是时间复杂度?如何分析一段代码?
一句话结论
时间复杂度是算法执行时间随输入规模 n 增长的渐进趋势,用大 O 表示;分析时只保留最高阶项,忽略常数与低阶项。
概念解释
- 输入规模 n:数组长度、链表节点数、字符串长度、矩阵边长等。
- 基本操作:一次比较、一次加减乘除、一次赋值等视为 O(1)。
- 渐进趋势:不关心具体毫秒数,只关心 n 增大时增长曲线属于哪一类。
原理流程
- 找出代码中执行次数与 n 相关的循环与递归。
- 写出执行次数关于 n 的表达式。
- 去掉常数系数与低阶项,保留最高阶。
- 嵌套循环相乘,顺序执行相加。
代码 / 示例
for (int i = 0; i < n; i++) { // 外层 O(n)
for (int j = i; j < n; j++) { // 内层平均 n/2 次
// O(1) 基本操作
}
}
// 总次数约 n(n-1)/2,去掉系数与低阶 → O(n²)
常见误区
- 误区:时间复杂度等于代码运行的秒数;正解:它是渐进增长量级,与机器速度、常数无关。
- 误区:循环写了几层就一定是几重幂;正解:还要看每轮的步进方式,
i *= 2是对数级。
追问
- Q:两个循环分别处理 n 和 m,总复杂度? A:顺序执行是 O(n+m),不是 O(n·m)。
- Q:嵌套但内层从 0 到 n,外层从 0 到 n/2? A:仍是 O(n²),系数 1/2 被忽略。
02.1.1.1-002 大 O 的严格定义是什么?
一句话结论
若存在正常数 c 和 n₀,使得对所有 n ≥ n₀ 都有 f(n) ≤ c·g(n),则记 f(n) = O(g(n)),即 g 是 f 的渐进上界。
概念解释
- f(n) 是实际代价,g(n) 是用来描述量级的函数。
- c 与 n₀ 的存在性说明:只要足够大的 n 之后被 g 压住即可,小 n 时不必成立。
- 大 O 描述上界,不代表精确运行时间。
原理流程
- 写出代价表达式 f(n)。
- 找一个更简单的 g(n) 包住它。
- 验证能否取到常数 c 使不等式成立。
- 记作 O(g(n))。
代码 / 图示
f(n) = 3n² + 5n + 7
取 g(n) = n²,c = 4,n₀ = 4:
n ≥ 4 时 3n² + 5n + 7 ≤ 4n² 成立
→ f(n) = O(n²)
常见误区
- 误区:大 O 是算法的平均运行时间;正解:大 O 是上界记号,平均/最坏是对输入分布的分类,二者正交。
- 误区:O(n) 一定比 O(n²) 快;正解:小 n 时常数项可能反转,大 O 只描述大 n 趋势。
追问
- Q:为什么定义里要带 n₀? A:渐进分析只关心规模足够大后的行为,允许小规模下不等式不成立。
- Q:O(n) 和 O(2n) 为什么写成同一个? A:常数系数被定义中的 c 吸收。
02.1.1.1-003 大 Ω、大 Θ、小 o、小 ω 分别表示什么?
一句话结论
大 Ω 是渐进下界,大 Θ 是渐进紧确界(上下界同阶),小 o 是严格上界(系数可任意小),小 ω 是严格下界;面试中最常用大 O 与大 Θ。
概念解释
- O:f ≤ c·g(上界,可能松)。
- Ω:f ≥ c·g(下界)。
- Θ:同时满足 O 与 Ω,即 f 与 g 同阶。
- o:对任意 c > 0 都有 f ≤ c·g,比值趋零;ω 对称。
原理流程
- 先确定实际代价的量级。
- 若只能保证上界写 O;若能证明上下界同阶写 Θ。
- 严谨论文与教材常用 Θ,工程面试通常写 O 表达量级。
代码 / 图示
归并排序:最坏与平均都是 n log n → Θ(n log n),也常写成 O(n log n)
哈希查找:平均 O(1),最坏 O(n),不能笼统写 Θ(1)
常见误区
- 误区:说"平均复杂度 O(1)"就意味着一定是紧确的;正解:平均是概率口径,紧确界需另证。
- 误区:O 与 Θ 可以随意互换;正解:O 允许更松,Θ 要求同阶,证明强度不同。
追问
- Q:二分查找的紧确复杂度? A:每次折半,比较次数 Θ(log n)。
- Q:为什么哈希表平均 O(1) 最坏 O(n)? A:平均假设哈希均匀、冲突随机;最坏全部冲突退化为链表。
02.1.1.1-004 常见复杂度从快到慢怎么排?
一句话结论
常见量级排序为 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!),实际选型按数据范围对照。
概念解释
- 对数级:折半、树形结构高度。
- 线性级:单趟扫描。
- 线性对数:比较排序的下界。
- 多项式:嵌套循环。
- 指数/阶乘:暴力枚举、子集排列。
原理流程
- 由 n 的上界判断可接受量级。
- n ≤ 10⁷ 可接近 O(n);n ≤ 10⁵ 需 O(n log n);n ≤ 10³ 可 O(n²);n ≤ 20 才考虑指数级。
- 对照候选算法的量级筛选方案。
代码 / 图示
量级:1 → log n → n → n log n → n² → n³ → 2^n → n!
增长:常数 折半 扫描 排序 双循环 三循环 子集 排列
常见误区
- 误区:O(n log n) 一定比 O(n²) 跑得快;正解:n 很小时常数与缓存可能反转,量级结论只在大 n 成立。
- 误区:指数级算法完全不能用;正解:n 很小(如 n ≤ 20)时可接受,配合剪枝。
追问
- Q:n = 10⁵ 时 O(n²) 为什么通常超时? A:约 10¹⁰ 次操作,远超常规时间预算。
- Q:O(log n) 为什么比 O(n) 快得多? A:每步把问题规模减半,步数随 n 对数增长。
02.1.1.1-005 循环执行次数如何对应到复杂度?
一句话结论
单趟线性扫描是 O(n);步长按倍数收缩是 O(log n);两层独立嵌套是 O(n²);步长递减的三角循环仍是 O(n²)。
概念解释
- 线性循环:
i每次加 1,跑 n 次。 - 对数循环:
i *= 2或i /= 2,跑 log₂n 次。 - 平方循环:两层各自独立遍历 n。
- 三角循环:内层起点随外层增大,总次数仍是二阶。
原理流程
- 列出每轮步进规则。
- 计算循环次数关于 n 的解析式。
- 取最高阶项。
代码 / 示例
for (int i = 1; i < n; i *= 2) { } // O(log n)
for (int i = 0; i < n; i++) { // O(n²)
for (int j = 0; j < n; j++) { }
}
for (int i = 0; i < n; i++) { // O(n²),总次数 n(n-1)/2
for (int j = i; j < n; j++) { }
}
常见误区
- 误区:内层
j = i就是 O(n);正解:总次数仍是 n²/2,量级 O(n²)。 - 误区:
i += 3会改变量级;正解:系数 1/3 被忽略,仍是 O(n)。
追问
- Q:
for (i=1; i<n; i=i*3)复杂度? A:O(log₃ n),换底后仍记 O(log n)。 - Q:两层循环分别到 n 和 m? A:O(n·m)。
02.1.1.1-006 顺序执行与嵌套执行的复杂度怎么合并?
一句话结论
顺序结构复杂度相加取高阶;嵌套结构复杂度相乘;同一算法取各部分中最高阶作为整体复杂度。
概念解释
- 相加:
T1(n) + T2(n),结果取增长更快的一项。 - 相乘:内层每执行一次都带动外层整体,
T1(n) × T2(n)。 - 分支:if/else 取两条路径中最坏的一条。
原理流程
- 逐段标注局部复杂度。
- 顺序段相加,嵌套段相乘。
- 化简后保留最高阶。
代码 / 示例
// 段一:O(n)
for (int i = 0; i < n; i++) { }
// 段二:O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { }
}
// 整体 O(n²),低阶 O(n) 被吸收
常见误区
- 误区:两段 O(n) 相加变成 O(2n);正解:系数忽略,仍是 O(n)。
- 误区:嵌套两段分别 O(n)、O(log n) 写成 O(n + log n);正解:嵌套相乘为 O(n log n)。
追问
- Q:一段 O(n) 后接一段 O(log n)? A:整体 O(n),取高阶。
- Q:循环体内调用一次 O(k) 的方法? A:整体 O(n·k),k 是该方法的规模。
02.1.1.1-007 空间复杂度怎么计算?
一句话结论
空间复杂度统计算法额外分配的内存(不含输入本身),看辅助数组、栈、队列、哈希表、递归深度随 n 的增长量级。
概念解释
- 输入空间:题目给的数组、字符串通常不计入额外空间。
- 辅助空间:新建的容器、临时变量、递归调用栈。
- 原地算法:只使用 O(1) 额外空间。
原理流程
- 列出代码中所有 new 出来的数据结构。
- 看其大小是否与 n 相关。
- 递归单独统计调用栈深度。
- 取最高阶作为空间复杂度。
代码 / 示例
int[] copy = Arrays.copyOf(nums, nums.length); // 辅助 O(n)
Map<Integer,Integer> map = new HashMap<>(); // 最坏 O(n)
int tmp = 0; // O(1)
常见误区
- 误区:把输入数组的大小算进空间复杂度;正解:空间复杂度一般指额外辅助空间。
- 误区:递归没有显式 new 数组就 O(1);正解:调用栈本身占用栈帧空间。
追问
- Q:排序的原地算法空间复杂度? A:快排递归栈 O(log n),堆排序 O(1),归并 O(n)。
- Q:哈希表最坏空间? A:与存储元素数同阶,最坏 O(n)。
02.1.1.1-008 递归调用的空间复杂度怎么算?
一句话结论
递归空间复杂度 = 递归深度 × 每层栈帧占用;每层常数空间则为 O(深度),深度为 n 即 O(n),折半递归为 O(log n)。
概念解释
- 栈帧:每次调用保存返回地址、参数、局部变量。
- 最大深度:同时驻留在栈上的调用层数。
- 尾递归若被编译器优化,栈帧可复用,但 Java、Python 默认不保证尾调用消除。
原理流程
- 画出递归树,求最长路径深度。
- 统计每层局部变量占用。
- 深度 × 单层空间即为栈空间。
代码 / 示例
// 反向递归打印链表:深度 n,栈空间 O(n)
void walk(ListNode p) {
if (p == null) return;
walk(p.next);
System.out.println(p.val);
}
常见误区
- 误区:递归只看递归次数,不看深度;正解:线性递归次数与深度同为 n,二叉递归次数指数级但深度为 O(log n) 或 O(h)。
- 误区:递归函数返回后栈帧立刻释放,所以空间很小;正解:未返回的祖先帧仍驻留栈上。
追问
- Q:深度 n 的递归为什么可能栈溢出? A:栈空间有限(常为 MB 级),过深会抛 StackOverflowError。
- Q:如何降低递归空间? A:改迭代、尾递归(依赖语言支持)、手动栈模拟。
02.1.1.1-009 最好、最坏、平均复杂度有什么区别?
一句话结论
最好复杂度对应最有利输入,最坏对应最不利输入,平均按输入分布求期望;面试默认讨论最坏情况,除非题目明确问平均。
概念解释
- 最好(best-case):输入排列最优,如顺序数据上的线性查找。
- 最坏(worst-case):输入最不利,如末尾才命中、全部冲突。
- 平均(average-case):假设输入服从某分布后的期望。
原理流程
- 分别构造最优、最坏输入。
- 计算两类输入下的操作次数。
- 平均需要先声明分布,再按概率加权。
代码 / 示例
线性查找 target:
最好:首元素命中 → O(1)
最坏:末尾命中或不存在 → O(n)
平均:均匀随机下期望约 n/2 → O(n)
常见误区
- 误区:平均复杂度一定比最坏低,可以用平均代替承诺;正解:线上常按最坏留容量,平均只在分布可控时有意义。
- 误区:只报最好复杂度给面试官;正解:必须主动说明最坏与平均,体现严谨性。
追问
- Q:快速排序的最好/最坏? A:最好与平均 O(n log n),最坏 O(n²)(极端有序或基准选择不当)。
- Q:哈希表查找的最好/最坏? A:最好 O(1),最坏 O(n)(全冲突)。
02.1.1.1-010 期望复杂度和均摊复杂度是一回事吗?
一句话结论
不是:期望复杂度对随机输入或随机化算法取概率平均;均摊复杂度针对固定操作序列,把偶尔昂贵的操作成本平摊到每次操作上,不依赖输入分布假设。
概念解释
- 期望:概率加权,前提是随机源或输入分布。
- 均摊:确定性分析,针对一个操作序列的最坏总代价除以操作次数。
- 均摊 O(1) 不等于单次操作 O(1),单次可能很贵。
原理流程
- 区分问题:是否存在随机化或概率分布。
- 随机场景用期望;连续操作场景(扩容、出队搬栈)用均摊。
- 两者都要说明适用前提。
代码 / 图示
动态数组连续插入 n 次:
某次扩容 O(n),但总代价 O(n),均摊每次 O(1)
不需要假设插入位置随机
常见误区
- 误区:均摊是"运气好时的平均";正解:均摊是对最坏操作序列的成本平摊,保证性更强。
- 误区:期望 O(1) 就不会出现 O(n) 操作;正解:期望平均低不排除单次长尾。
追问
- Q:随机化快排用哪种分析? A:期望复杂度,基准随机抽取后比较次数期望 O(n log n)。
- Q:两栈倒腾队列属于哪种? A:均摊分析,每个元素最多搬一次,出队均摊 O(1)。
02.1.1.1-011 为什么常数项和低阶项可以忽略?
一句话结论
大 O 描述大 n 下的增长趋势;n 足够大时,高阶项碾压常数与低阶项,因此 5n² + 3n + 10 记为 O(n²)。
概念解释
- 高阶项随 n 增长最快,决定量级。
- 常数系数被定义中的 c 吸收。
- 低阶项在大 n 下占比趋近于零。
原理流程
- 拆分表达式各次幂。
- 保留最高次幂。
- 去掉其系数。
代码 / 示例
f(n) = 12n³ + 8n² + 3
n → ∞ 时 n³ 主导 → O(n³)
常见误区
- 误区:忽略常数后算法对比就不用看常数;正解:量级相同时常数、缓存、分支预测对实际耗时影响很大。
- 误区:低阶项在小 n 下也不重要;正解:小数据上低阶项与常数往往决定体感速度。
追问
- Q:O(n) 与 O(1000n) 是同一量级吗? A:是,大 O 下同写 O(n),但实际常数差三个数量级。
- Q:什么时候必须看常数? A:量级相同、数据规模不大、或做工程性能调优时。
02.1.1.1-012 对数复杂度的底数为什么可以随便换?
一句话结论
换底公式 log_b n = log_a n / log_a b,分母是常数,被大 O 吸收,因此 O(log₂ n)、O(ln n) 统一记为 O(log n)。
概念解释
- 不同底数只差一个常数倍率。
- 算法中折半、按倍数扩张对应对数级。
- 底数不影响量级归类。
原理流程
- 写出
log_b n。 - 用换底公式转成任意底数。
- 常数倍率忽略,记 O(log n)。
代码 / 示例
log₂ n = ln n / ln 2 = 1.4427 · ln n
系数 1.4427 被吸收 → 都是 O(log n)
常见误区
- 误区:必须写清底数;正解:渐进分析中底数省略,只写 O(log n)。
- 误区:
log n与n log n是一类;正解:后者多乘一个 n,常见于比较排序。
追问
- Q:树高为什么是 O(log n)? A:平衡树每层约两倍分支,高度随节点数对数增长。
- Q:以 10 为底的对数循环? A:仍是 O(log n)。
02.1.1.1-013 数据范围如何反推可接受的复杂度?
一句话结论
按题目给出的 n 上界对照常见量级:n ≤ 20 可指数级,n ≤ 10³ 可 O(n²),n ≤ 10⁵ 需 O(n log n),n ≤ 10⁷ 才接近 O(n),反推时还要留常数与运行余量。
概念解释
- 常规时间预算约每秒 10⁷~10⁸ 次简单操作(语言与机器不同,需以实测为准)。
- 量级先定方向,常数后做优化。
- 多组测试用例时总量按 Σn 或 n·组数估算。
原理流程
- 读题取 n 的上界与组数。
- 估算各量级下的操作次数。
- 落在预算内的量级作为目标解法。
- 暴力能过则先写暴力,再按要求优化。
代码 / 图示
n ≤ 20 → 2^n / n! 可接受
n ≤ 10³ → n² 约 10⁶
n ≤ 10⁵ → n² 约 10¹⁰ 超时,需 n log n
n ≤ 10⁷ → 接近线性,避免对数以外的额外因子
常见误区
- 误区:只看单组 n,忘了多组数据累加;正解:组数乘进总操作量估算。
- 误区:理论量级达标就一定能过;正解:大常数、IO、内存分配也可能超时。
追问
- Q:n = 10⁵ 时 O(n²) 还有救吗? A:先看能否剪枝降到平均低阶,否则需换 O(n log n) 方案。
- Q:空间上限怎么反推? A:按内存预算除以元素大小,估算可开多大辅助数组。
02.1.1.1-014 有哪些容易被忽略的隐藏成本?
一句话结论
字符串不可变拼接、substring 复制、哈希冲突链化、随机访问底层数组、自动装箱、容器扩容 rehash,都会在 O(1) 表象下藏着额外代价。
概念解释
- 不可变字符串:每次拼接生成新串,链式拼接是 O(n²)。
- 哈希表:均摊 O(1),冲突严重时退化。
- 随机访问:链表
get(i)需沿指针移动,不是 O(1)。
原理流程
- 识别表面 O(1) 的调用。
- 追溯其底层是否拷贝、遍历或 rehash。
- 把隐藏成本计入整体复杂度。
代码 / 示例
// 差:循环内 + 拼接,字符串不可变,整体 O(n²)
String s = "";
for (String w : words) s += w;
// 好:StringBuilder 预分配,摊还 O(n)
StringBuilder sb = new StringBuilder(n);
for (String w : words) sb.append(w);
常见误区
- 误区:
map.get/put永远 O(1);正解:哈希均匀时平均 O(1),冲突退化另算。 - 误区:
list.get(i)是随机访问;正解:ArrayList 是 O(1),LinkedList 是 O(i)。
追问
- Q:为什么 StringBuilder 更快? A:内部可变字符数组,按需扩容,避免每步新建字符串。
- Q:ArrayList 扩容代价? A:扩容时整体拷贝,均摊到每次追加为 O(1)。
02.1.1.1-015 多项式复杂度与指数复杂度的分界在哪?
一句话结论
存在多项式时间解法即属多项式类;枚举全部子集/排列带来 2^n 或 n! 是指数级;分界点在于能否避免逐一枚举。
概念解释
- 多项式:n、n log n、n²、n³。
- 指数:2^n、3^n、n!。
- n 稍大时指数级完全不可行,需剪枝、DP、贪心或近似。
原理流程
- 看解法是否枚举所有组合/排列。
- 枚举规模是 2^n(子集)还是 n!(排列)。
- 若存在状态复用或结构性质,可降到多项式。
代码 / 图示
子集枚举:2^n
全排列:n!
背包 DP:状态数 n·W → 多项式
常见误区
- 误区:回溯题都是指数级且无法优化;正解:满足无后效性时可转 DP 多项式求解。
- 误区:2^n 与 n! 增长差不多;正解:n! 比 2^n 增长更快,排列枚举更敏感于 n。
追问
- Q:n = 20 时 2^n 多大? A:约一百万,剪枝后尚可;n = 40 已达万亿级。
- Q:判定多项式与指数的实践意义? A:决定是否必须寻找结构优化,而不是硬跑枚举。
02.1.1.1-016 什么是原地算法?辅助空间怎么界定?
一句话结论
原地算法只使用 O(1) 量级额外空间(个别递归栈或少量临时变量除外),不新建与输入同阶的数据结构;是否原地要按题目口径确认。
概念解释
- 原地:交换、翻转、覆盖在输入上完成。
- 非原地:另开数组/哈希表/栈保存结果。
- 争议口径:递归栈、输出数组是否计入,需与题目约定一致。
原理流程
- 区分输入空间、输出空间、辅助空间。
- 辅助空间为 O(1) 即称原地。
- 若题目要求原地,优先双指针交换覆盖。
代码 / 示例
// 原地反转数组:O(1) 额外空间
void reverse(int[] a) {
int l = 0, r = a.length - 1;
while (l < r) {
int t = a[l]; a[l] = a[r]; a[r] = t;
l++; r--;
}
}
常见误区
- 误区:递归翻转链表是原地;正解:递归栈 O(n),通常不算严格原地。
- 误区:输出结果数组算辅助空间;正解:多数题面把输出空间单列,不计入额外空间,需看题面约定。
追问
- Q:原地修改会不会破坏输入? A:会,若后续还要用原数组需先备份;面试时先确认输入是否可改。
- Q:原地排序有哪些? A:堆排序 O(1)、快排平均 O(log n) 栈;归并非原地。
02.1.1.1-017 如何向面试官口头汇报复杂度?
一句话结论
按"时间 + 空间 + 最坏/平均/均摊口径 + 关键依据"四要素汇报,先给结论量级,再说明由哪段循环或数据结构决定。
概念解释
- 结论先行:O(?) 时间、O(?) 空间。
- 口径明确:最坏、平均还是均摊。
- 依据可追溯:哪一层循环、哪个容器。
原理流程
- 定位主循环/递归/容器规模。
- 得出量级并说明口径。
- 补充可优化方向与代价。
代码 / 图示
汇报模板:
"时间最坏 O(n),左右指针各移动一次;
空间 O(1),只用了几个指针变量;
输入有序前提下成立。"
常见误区
- 误区:只说"很快/最优"不报量级;正解:必须给出大 O 与口径。
- 误区:空间复杂度漏说递归栈;正解:涉及递归要补一句栈空间量级。
追问
- Q:被问"为什么是 O(n)"怎么答? A:每个元素最多被访问常数次,总操作与 n 同阶。
- Q:算法有多种复杂度怎么报? A:分别报最坏与平均,并说明触发条件。
02.1.1.1-018 复杂度分析常见的反例有哪些?
一句话结论
常见反例包括:嵌套但步长不同、哈希表被误当 O(1) 无条件、字符串拼接被当 O(n)、链表随机访问被当 O(1)、递归深度被忽略。
概念解释
- 反例一:两层循环看似 O(n²),内层实际只跑常数次。
- 反例二:哈希在最坏冲突下降级。
- 反例三:不可变串拼接链式累积成平方。
- 反例四:链表按索引访问是线性。
原理流程
- 逐行确认数据结构底层语义。
- 核对循环步进与容器代价。
- 对可疑 O(1) 调用追问其实现。
代码 / 图示
易错对照:
字符串链式拼接 误 O(n) 实 O(n²)
LinkedList.get 误 O(1) 实 O(n)
HashMap 全冲突 误 O(1) 实 O(n)
递归深度 n 误 O(1) 实 O(n) 栈空间
常见误区
- 误区:按数据结构名字套量级,不看操作;正解:量级依赖具体操作(get 按索引 vs 按值)。
- 误区:先写代码后补复杂度;正解:思路阶段就估算,超范围及时换框架。
追问
- Q:ArrayList 删除末尾与删除中间? A:末尾 O(1),中间需平移 O(n)。
- Q:String 与 StringBuilder 长度不同时复杂度差多少? A:链式拼接平方,Builder 线性。