02.1.1.2 递归复杂度与主定理
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架 / 02.1.1 复杂度与解题框架
02.1.1.2-001 递归算法的复杂度怎么入手分析?
一句话结论
先写出递归关系式 T(n) = 子问题代价 + 合并代价,再用主定理、递归树或代入法求解;空间复杂度另算递归深度。
概念解释
- 子问题代价:递归调用次数 × 每次规模。
- 合并代价:当前层切割、拼接、扫描等非递归工作。
- 关系式必须能表达 n 到更小规模的递推。
原理流程
- 确定基准情形 T(1) 或 T(0)。
- 写出 n 层的递推式。
- 选主定理、递归树或代入法求解。
- 补算递归栈空间。
代码 / 示例
归并排序:
T(1) = O(1)
T(n) = 2·T(n/2) + O(n)
→ 主定理 case 2 → O(n log n)
常见误区
- 误区:只数递归调用次数;正解:还要算每层合并/扫描的代价。
- 误区:递归复杂度一定比迭代高;正解:量级相同时常数与栈空间才是差异点。
追问
- Q:递归式写不出标准形式怎么办? A:用递归树逐层求和,或代入法猜测上界后归纳证明。
- Q:子问题规模不整除怎么办? A:向下取整不影响渐进量级,按 n/b 处理。
02.1.1.2-002 主定理的标准形式是什么?
一句话结论
对 T(n) = a·T(n/b) + f(n)(a ≥ 1,b > 1,f(n) 渐进正),比较 f(n) 与 n^log_b a 的量级,分三种情形得到 T(n)。
概念解释
- a:每层分裂出的子问题个数。
- b:每个子问题规模相对原问题的收缩比例。
- f(n):当前层切割与合并的代价。
- 临界函数:
n^log_b a,即纯递归树叶节点量级。
原理流程
- 读出 a、b、f(n)。
- 计算
n^log_b a。 - 比较 f(n) 与临界函数的大小关系。
- 落入对应情形得出结论。
代码 / 图示
T(n) = a·T(n/b) + f(n)
临界规模:n^(log_b a)
case 1:f 低阶 → T(n) = Θ(n^log_b a)
case 2:f 同阶 → T(n) = Θ(n^log_b a · log n)
case 3:f 高阶 → T(n) = Θ(f(n))
常见误区
- 误区:主定理对任意递归式都适用;正解:要求子问题等规模、等数量,形如 aT(n/b)。
- 误区:f(n) 与临界函数直接比大小即可;正解:case 1/3 还要求多项式差距(大 o / 大 Ω),相邻量级走 case 2。
追问
- Q:a = 2、b = 2,临界函数是多少? A:
n^log₂2 = n。 - Q:a = 1、b = 2,临界函数? A:
n^0 = 1,对应折半递归。
02.1.1.2-003 主定理三种情形分别怎么取结果?
一句话结论
f(n) 低于临界函数多项式阶取叶节点量级;同阶乘 log n;高于临界函数且满足正则条件取 f(n) 自身量级。
概念解释
- case 1:
f(n) = O(n^log_b a - ε),叶节点主导。 - case 2:
f(n) = Θ(n^log_b a),层代价与叶节点同阶。 - case 3:
f(n) = Ω(n^log_b a + ε),且 a·f(n/b) ≤ c·f(n),根层主导。
原理流程
- 计算 d = log_b a。
- 看 f(n) 的阶与 d 的关系。
- 按情形套结论;case 3 额外验证正则条件。
代码 / 示例
T(n) = 2T(n/2) + n → d=1,f=Θ(n) → Θ(n log n)
T(n) = T(n/2) + 1 → d=0,f=Θ(1) → Θ(log n)
T(n) = 2T(n/2) + n² → d=1,f=Ω(n²) → Θ(n²)
常见误区
- 误区:case 2 忘记乘 log n;正解:同阶时总层数 log n,每层代价同阶,乘上 log n。
- 误区:case 3 不需要验证正则条件;正解:不满足正则条件时主定理 case 3 不能直接套用。
追问
- Q:
T(n)=4T(n/2)+n属于哪类? A:d=2,f=O(n²) 低阶 → Θ(n²)。 - Q:
T(n)=4T(n/2)+n²? A:同阶 → Θ(n² log n)。
02.1.1.2-004 主定理不适用时怎么办?
一句话结论
子问题规模不等、数量不固定、f(n) 夹在两阶之间时,改用递归树逐层求和,或代入法猜测上界后数学归纳证明。
概念解释
- 不等规模:如
T(n)=T(n-1)+T(n/2)+O(n)。 - 非标准分裂:子问题个数随 n 变化。
- 临界夹缝:f(n) 与临界函数只差对数因子,需单独展开。
原理流程
- 画递归树:根层代价 f(n),逐层展开子问题。
- 统计每层总代价与层数。
- 求和取高阶;必要时代入法验证。
代码 / 图示
递归树:
第 0 层:f(n)
第 1 层:a·f(n/b)
…
第 h 层:叶节点
总代价 = 各层代价之和
常见误区
- 误区:递归式长得像就能套主定理;正解:先核对 a、b 是否恒定、子问题是否等规模。
- 误区:递归树只数叶节点;正解:每层内部工作 f 的代价也要计入。
追问
- Q:代入法的步骤? A:猜测量级 g(n),假设 n-1 成立,代入递推式验证 n 成立。
- Q:递归树层数怎么定? A:按子问题规模收缩到 1 的路径长度计算。
02.1.1.2-005 递归树法怎么逐层求和?
一句话结论
把递归式展开成树,写出每层总代价与层数,等比或等差求和后保留最高阶;叶节点层与内部层分别估算。
概念解释
- 每层总代价:该层所有节点 f(子规模) 之和。
- 层数:规模从 n 收缩到 1 的深度。
- 求和形式:等比级数按公比收敛或发散。
原理流程
- 展开根、子节点、孙节点。
- 归纳第 k 层的节点数与单节点代价。
- 写出层代价通项。
- 对层数求和并取高阶。
代码 / 示例
T(n)=2T(n/2)+n
第 k 层:2^k 个节点,每个代价 n/2^k → 层代价 n
层数 log₂n → 总代价 n·log n
常见误区
- 误区:每层代价都按根层 f(n) 算;正解:子问题规模缩小,单节点代价随之下降。
- 误区:忽略叶节点层;正解:叶节点基准代价也要计入,低阶时可被吸收。
追问
- Q:层代价递增的树怎么求和? A:按等比级数公比 r > 1,总代价由最底层主导。
- Q:层代价递减呢? A:公比 r < 1,总代价由根层主导。
02.1.1.2-006 二分查找的递归复杂度是多少?
一句话结论
递归二分每次排除一半,T(n)=T(n/2)+O(1),主定理 case 2 得 Θ(log n),递归栈空间 O(log n)。
概念解释
- 每次比较后只进入一个子问题。
- 规模折半,层数 log₂n。
- 每层只做一次比较与下标计算。
原理流程
- 写出递推式。
- a=1、b=2,临界函数 n⁰=1,f(n)=O(1) 同阶。
- 套 case 2 → Θ(log n)。
代码 / 示例
int search(int[] a, int l, int r, int t) {
if (l > r) return -1;
int m = l + (r - l) / 2;
if (a[m] == t) return m;
return a[m] < t ? search(a, m + 1, r, t)
: search(a, l, m - 1, t);
}
常见误区
- 误区:二分是 O(n);正解:每次折半,对数级。
- 误区:递归二分空间 O(1);正解:调用栈深度 O(log n)。
追问
- Q:迭代二分空间多少? A:O(1),只用左右下标变量。
- Q:二分前提条件? A:区间有序(或具备可判断目标在左/右的单调性)。
02.1.1.2-007 归并排序的递归复杂度怎么推?
一句话结论
T(n)=2T(n/2)+O(n),两个等规模子问题加一层 O(n) 合并,主定理 case 2 得 Θ(n log n),空间 O(n)(合并临时数组)。
概念解释
- 分裂:递归切成两半。
- 合并:双指针归并两个有序段,O(n)。
- 稳定排序,不依赖输入有序性。
原理流程
- 递推式:两半递归 + 线性合并。
- a=2、b=2,临界函数 n,f(n)=n 同阶。
- 结论 Θ(n log n);临时数组 O(n)。
代码 / 示例
void mergeSort(int[] a, int l, int r, int[] tmp) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, l, m, tmp);
mergeSort(a, m + 1, r, tmp);
merge(a, l, m, r, tmp); // O(n) 双指针合并
}
常见误区
- 误区:归并是原地排序;正解:标准归并需 O(n) 临时空间。
- 误区:归并最坏会退化;正解:分裂与合并结构固定,最坏仍是 n log n。
追问
- Q:归并为什么稳定? A:合并时相等元素先取左侧,保持相对顺序。
- Q:n log n 的 log 来自哪里? A:递归层数,每层线性合并。
02.1.1.2-008 快速排序的平均与最坏复杂度分别是什么?
一句话结论
平均 Θ(n log n),最坏 Θ(n²)(基准极端不平衡);递归栈平均 O(log n),最坏 O(n)。
概念解释
- 分区:选基准把数组划为小于/大于两部分。
- 平衡时两子问题约 n/2。
- 最坏时一侧恒为空,退化为线性递归链。
原理流程
- 平均:递推近似
2T(n/2)+O(n)→ n log n。 - 最坏:
T(n)=T(n-1)+O(n)→ n²。 - 随机选基准或三数取中降低最坏概率。
代码 / 示例
int partition(int[] a, int l, int r) {
int pivot = a[r], i = l;
for (int j = l; j < r; j++) {
if (a[j] < pivot) swap(a, i++, j);
}
swap(a, i, r);
return i;
}
常见误区
- 误区:快排最坏也是 n log n;正解:极端输入下退化为 n²。
- 误区:快排稳定;正解:分区交换可能改变相等元素相对顺序,不稳定。
追问
- Q:如何避免最坏? A:随机化基准、三数取中;工程库排序多为混合策略。
- Q:快排空间复杂度? A:递归栈平均 O(log n),最坏 O(n)。
02.1.1.2-009 朴素斐波那契递归为什么是指数级?
一句话结论
朴素递归重复计算大量相同子问题,递归树节点数随层数指数增长,时间 O(2^n),栈深 O(n)。
概念解释
F(n)=F(n-1)+F(n-2)。- 同一
F(k)被反复展开,子问题重叠。 - 树节点数近似斐波那契量级,指数增长。
原理流程
- 画递归树:每层节点数约翻倍。
- 深度 n,节点数 2^n 量级。
- 记忆化后每个子问题只算一次。
代码 / 示例
// 朴素:O(2^n)
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// 记忆化:O(n)
int fib(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}
常见误区
- 误区:递归写出来就是线性;正解:重叠子问题不记忆化会指数膨胀。
- 误区:记忆化后空间仍是 O(1);正解:memo 数组 O(n),递归栈 O(n)。
追问
- Q:迭代 DP 版复杂度? A:时间 O(n),空间 O(1)(只保留前两项)。
- Q:矩阵快速幂能到多少? A:O(log n),属进阶优化。
02.1.1.2-010 记忆化之后复杂度口径怎么算?
一句话结论
记忆化后复杂度 = 不同状态数 × 每个状态的转移代价;空间 = 状态数 + 递归栈。
概念解释
- 状态:参数取值组合。
- 转移:每个状态内部的循环或选择。
- 重复命中缓存不再展开。
原理流程
- 列出状态空间规模。
- 统计单状态转移代价。
- 相乘得时间;状态表 + 栈深得空间。
代码 / 图示
背包 DP:状态 n·W,每状态枚举选/不选 O(1)
→ 时间 O(nW),空间 O(nW)(可滚动到 O(W))
常见误区
- 误区:记忆化只省时间不占空间;正解:缓存表本身占空间。
- 误区:状态数按递归次数算;正解:按不同参数组合数算,重复命中不计。
追问
- Q:二维状态 (i, j) 状态数多少? A:i 范围 × j 范围。
- Q:记忆化递归与递推 DP 复杂度一致吗? A:状态与转移相同则量级一致,递归多一份栈空间。
02.1.1.2-011 递归深度与栈溢出有什么关系?
一句话结论
每次递归调用占用一个栈帧,深度超过线程栈上限即抛栈溢出;线性递归深度为 n,n 大时必须改迭代或手动栈。
概念解释
- 栈上限:受运行时配置限制,常见为 MB 级。
- 栈帧:返回地址、参数、局部变量。
- 尾调用消除:部分语言可复用帧,Java 默认不保证。
原理流程
- 估算最长递归路径深度。
- 对照栈预算判断风险。
- 高风险场景改迭代或显式栈。
代码 / 示例
链表长度 10 万,递归反转:
深度 10 万帧 → 极易 StackOverflowError
迭代反转:O(1) 栈空间
常见误区
- 误区:递归次数少就不会溢出;正解:深度由最长路径决定,与总次数无关。
- 误区:JVM 会自动扩栈;正解:栈大小可配置但有上限,深递归不可靠。
追问
- Q:如何把递归改成迭代? A:用显式栈保存状态,按后进先出模拟调用顺序。
- Q:尾递归为什么省空间? A:最后一步是调用自身,当前帧可被覆盖(需运行时支持)。
02.1.1.2-012 分治算法的复杂度如何分解?
一句话结论
分治复杂度 = 分解代价 + 子问题递归 + 合并代价;先写递推式,再按主定理或递归树求解。
概念解释
- 分解:切分子问题。
- 治理:递归求解各子问题。
- 合并:汇总子结果。
原理流程
- 确定子问题个数与规模。
- 写出合并层代价。
- 递推求解并核对空间。
代码 / 图示
分治通用式:
T(n) = a·T(n/b) + D(n) + C(n)
D:分解代价,C:合并代价
常见误区
- 误区:分治一定比暴力快;正解:合并代价过高时(如 O(n²))整体未必占优。
- 误区:分治空间总是 O(1);正解:合并缓冲、递归栈都要计入。
追问
- Q:归并的分解与合并代价? A:分解 O(1)(按下标切),合并 O(n)。
- Q:分治适合什么问题? A:子问题同构、可独立求解、合并代价可控。
02.1.1.2-013 子问题规模不整除 b 时怎么处理?
一句话结论
向下取整或向上取整在渐进分析中不影响量级,按 n/b 代入主定理即可;只有当取整导致规模剧烈失衡时才需单独讨论。
概念解释
- 奇数长度切两半:
⌊n/2⌋与⌈n/2⌉。 - 差异最多 1,渐进同阶。
- 极端失衡(一侧 n-1)不能按 n/2 处理。
原理流程
- 写出实际切分规模。
- 确认两侧同阶后按 n/b 近似。
- 若失衡,改按最坏一侧规模列递推。
代码 / 示例
切分 [l, r],m = l + (r-l)/2
左段 m-l+1,右段 r-m,差 ≤ 1
→ 两侧均为 Θ(n/2)
常见误区
- 误区:取整会改变大 O;正解:常数级差异被吸收。
- 误区:所有切分都能按 n/2 近似;正解:分区失衡时必须按实际比例。
追问
- Q:快排最坏一侧 n-1 怎么写递推? A:
T(n)=T(n-1)+O(n),不能套 n/2。 - Q:二叉树递归左右子树规模? A:按实际高度 h 分析,平衡时 h=log n。
02.1.1.2-014 指数级递归如何判断剪枝空间?
一句话结论
先看子问题是否重叠(可记忆化/DP),再看是否存在单调性或约束可提前排除分支;无结构可利用时才接受指数级并限制 n。
概念解释
- 重叠子问题:重复状态可缓存。
- 约束剪枝:不满足条件的分支提前返回。
- 单调性:可缩小搜索方向。
原理流程
- 画递归树找重复节点。
- 检查状态是否可复用。
- 列出可提前终止的条件。
- 估算剪枝后最坏量级。
代码 / 图示
朴素子集枚举 2^n
约束:和超过目标即剪枝 → 实际分支减少
重叠状态:背包类可转 DP O(nW)
常见误区
- 误区:加了剪枝就一定多项式;正解:剪枝只改善平均,最坏仍可能指数。
- 误区:递归树所有分支都要走完;正解:满足边界即可提前回溯。
追问
- Q:回溯与递归的关系? A:回溯是带状态撤销的递归框架,复杂度按决策树规模。
- Q:什么信号提示可转 DP? A:子问题重叠且满足无后效性。
02.1.1.2-015 DP 题的复杂度口径为什么是状态数乘转移代价?
一句话结论
DP 把递归展开成状态表,每个状态只计算一次,时间 = 状态总数 × 单状态枚举转移的代价;空间 = 状态表大小。
概念解释
- 状态:DP 表的一个条目。
- 转移:从前驱状态推当前状态的选择循环。
- 无后效性:当前状态决定未来,不受路径影响。
原理流程
- 确定状态维度与取值范围。
- 统计状态总数。
- 单状态看转移循环长度。
- 相乘得时间,表长得空间。
代码 / 示例
最长递增子序列:状态 n,单状态往前扫 O(n)
→ 时间 O(n²),空间 O(n)
优化二分后:时间 O(n log n)
常见误区
- 误区:DP 时间看循环套了几层就写几阶;正解:以状态数 × 转移代价为准。
- 误区:滚动数组不改变状态数;正解:滚动只压缩空间,时间量级不变。
追问
- Q:背包二维状态复杂度? A:O(n·W),W 为容量。
- Q:区间 DP 状态数? A:区间数 O(n²),转移 O(n),整体 O(n³)。
02.1.1.2-016 递归转迭代后空间复杂度如何回收?
一句话结论
递归转迭代后不再保留调用栈,显式分配的循环变量为 O(1);若仍用手动栈模拟,空间与原递归深度同阶。
概念解释
- 直接迭代:状态用变量保存,无栈。
- 手动栈:把栈帧内容压入显式容器,空间等价递归。
- 记忆化表在迭代版本中仍保留。
原理流程
- 判断能否用变量递推(尾递归、线性递推)。
- 不能则用显式栈保存待处理节点。
- 统计容器最大占用。
代码 / 示例
// 迭代斐波那契:O(1) 空间
int fib(int n) {
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b; a = b; b = c;
}
return n == 0 ? a : b;
}
常见误区
- 误区:改成循环就一定 O(1) 空间;正解:需要保存中间层时仍要栈或数组。
- 误区:迭代一定比递归快;正解:量级相同时差异主要在栈开销与缓存。
追问
- Q:树的后序遍历迭代版空间? A:显式栈 O(h),与递归相同。
- Q:什么递归容易直接迭代化? A:尾递归、线性递推、计数式递归。
02.1.1.2-017 常见递归复杂度对照有哪些?
一句话结论
折半递归 O(log n)、双分支折半 O(n log n)、单链递归 O(n)、双分支不折半 O(2^n)、阶乘枚举 O(n!)。
概念解释
- 分支数与收缩比例共同决定量级。
- 叶节点数与层代价谁主导看主定理情形。
原理流程
- 识别 a(分支数)与 b(收缩比)。
- 对照递推形式查表。
- 特殊枚举形式单独标注。
代码 / 图示
T(n)=T(n/2)+O(1) → O(log n)
T(n)=2T(n/2)+O(n) → O(n log n)
T(n)=T(n-1)+O(1) → O(n)
T(n)=2T(n-1)+O(1) → O(2^n)
T(n)=n·T(n-1)+O(1) → O(n!)
常见误区
- 误区:分支多就一定指数;正解:分支多但规模快速收缩仍可能多项式。
- 误区:层数深就一定慢;正解:还要看每层代价与节点总数。
追问
- Q:
T(n)=3T(n/3)+O(n)? A:case 2 → O(n log n)。 - Q:
T(n)=T(n-2)+O(1)? A:仍是 O(n),步长 2 被吸收。
02.1.1.2-018 递推式分析时容易漏掉什么代价?
一句话结论
容易漏掉:递归外的扫描/合并、哈希表与临时数组、递归栈空间、字符串与集合拷贝;分析时必须把这些并入对应层代价。
概念解释
- 层内工作:除调用外的循环、查找、拷贝。
- 附加结构:缓存表、临时数组。
- 栈空间:单独统计,不混入时间。
原理流程
- 逐行标注非递归语句代价。
- 识别新建容器及其规模。
- 时间递推式与空间清单分别成文。
代码 / 图示
易漏清单:
合并段扫描 O(n)
排序子数组 O(n log n)
临时拷贝 O(n)
递归栈 O(h)
常见误区
- 误区:递推式只写递归调用项;正解:当前层工作 f(n) 必须写全。
- 误区:空间只看 new 出来的对象;正解:调用栈、迭代器、临时引用都要盘点。
追问
- Q:递归中用了全局缓存表,空间怎么算? A:缓存表按状态数 O(状态数),另加递归栈 O(h)。
- Q:合并里用了排序? A:把排序代价写进 f(n),整体重新评估量级。