罗罗编程学习记录
本页内容 展开查看

02.1.1.2 递归复杂度与主定理

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架 / 02.1.1 复杂度与解题框架

02.1.1.2-001 递归算法的复杂度怎么入手分析?

一句话结论

先写出递归关系式 T(n) = 子问题代价 + 合并代价,再用主定理、递归树或代入法求解;空间复杂度另算递归深度。

概念解释

  • 子问题代价:递归调用次数 × 每次规模。
  • 合并代价:当前层切割、拼接、扫描等非递归工作。
  • 关系式必须能表达 n 到更小规模的递推。

原理流程

  1. 确定基准情形 T(1) 或 T(0)。
  2. 写出 n 层的递推式。
  3. 选主定理、递归树或代入法求解。
  4. 补算递归栈空间。

代码 / 示例

归并排序:
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,即纯递归树叶节点量级。

原理流程

  1. 读出 a、b、f(n)。
  2. 计算 n^log_b a。
  3. 比较 f(n) 与临界函数的大小关系。
  4. 落入对应情形得出结论。

代码 / 图示

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),根层主导。

原理流程

  1. 计算 d = log_b a。
  2. 看 f(n) 的阶与 d 的关系。
  3. 按情形套结论;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) 与临界函数只差对数因子,需单独展开。

原理流程

  1. 画递归树:根层代价 f(n),逐层展开子问题。
  2. 统计每层总代价与层数。
  3. 求和取高阶;必要时代入法验证。

代码 / 图示

递归树:
第 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 的深度。
  • 求和形式:等比级数按公比收敛或发散。

原理流程

  1. 展开根、子节点、孙节点。
  2. 归纳第 k 层的节点数与单节点代价。
  3. 写出层代价通项。
  4. 对层数求和并取高阶。

代码 / 示例

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。
  • 每层只做一次比较与下标计算。

原理流程

  1. 写出递推式。
  2. a=1、b=2,临界函数 n⁰=1,f(n)=O(1) 同阶。
  3. 套 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)。
  • 稳定排序,不依赖输入有序性。

原理流程

  1. 递推式:两半递归 + 线性合并。
  2. a=2、b=2,临界函数 n,f(n)=n 同阶。
  3. 结论 Θ(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。
  • 最坏时一侧恒为空,退化为线性递归链。

原理流程

  1. 平均:递推近似 2T(n/2)+O(n) → n log n。
  2. 最坏:T(n)=T(n-1)+O(n) → n²。
  3. 随机选基准或三数取中降低最坏概率。

代码 / 示例

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) 被反复展开,子问题重叠。
  • 树节点数近似斐波那契量级,指数增长。

原理流程

  1. 画递归树:每层节点数约翻倍。
  2. 深度 n,节点数 2^n 量级。
  3. 记忆化后每个子问题只算一次。

代码 / 示例

// 朴素: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 记忆化之后复杂度口径怎么算?

一句话结论

记忆化后复杂度 = 不同状态数 × 每个状态的转移代价;空间 = 状态数 + 递归栈。

概念解释

  • 状态:参数取值组合。
  • 转移:每个状态内部的循环或选择。
  • 重复命中缓存不再展开。

原理流程

  1. 列出状态空间规模。
  2. 统计单状态转移代价。
  3. 相乘得时间;状态表 + 栈深得空间。

代码 / 图示

背包 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 默认不保证。

原理流程

  1. 估算最长递归路径深度。
  2. 对照栈预算判断风险。
  3. 高风险场景改迭代或显式栈。

代码 / 示例

链表长度 10 万,递归反转:
深度 10 万帧 → 极易 StackOverflowError
迭代反转:O(1) 栈空间

常见误区

  • 误区:递归次数少就不会溢出;正解:深度由最长路径决定,与总次数无关。
  • 误区:JVM 会自动扩栈;正解:栈大小可配置但有上限,深递归不可靠。

追问

  • Q:如何把递归改成迭代? A:用显式栈保存状态,按后进先出模拟调用顺序。
  • Q:尾递归为什么省空间? A:最后一步是调用自身,当前帧可被覆盖(需运行时支持)。

02.1.1.2-012 分治算法的复杂度如何分解?

一句话结论

分治复杂度 = 分解代价 + 子问题递归 + 合并代价;先写递推式,再按主定理或递归树求解。

概念解释

  • 分解:切分子问题。
  • 治理:递归求解各子问题。
  • 合并:汇总子结果。

原理流程

  1. 确定子问题个数与规模。
  2. 写出合并层代价。
  3. 递推求解并核对空间。

代码 / 图示

分治通用式:
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 处理。

原理流程

  1. 写出实际切分规模。
  2. 确认两侧同阶后按 n/b 近似。
  3. 若失衡,改按最坏一侧规模列递推。

代码 / 示例

切分 [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。

概念解释

  • 重叠子问题:重复状态可缓存。
  • 约束剪枝:不满足条件的分支提前返回。
  • 单调性:可缩小搜索方向。

原理流程

  1. 画递归树找重复节点。
  2. 检查状态是否可复用。
  3. 列出可提前终止的条件。
  4. 估算剪枝后最坏量级。

代码 / 图示

朴素子集枚举 2^n
约束:和超过目标即剪枝 → 实际分支减少
重叠状态:背包类可转 DP O(nW)

常见误区

  • 误区:加了剪枝就一定多项式;正解:剪枝只改善平均,最坏仍可能指数。
  • 误区:递归树所有分支都要走完;正解:满足边界即可提前回溯。

追问

  • Q:回溯与递归的关系? A:回溯是带状态撤销的递归框架,复杂度按决策树规模。
  • Q:什么信号提示可转 DP? A:子问题重叠且满足无后效性。

02.1.1.2-015 DP 题的复杂度口径为什么是状态数乘转移代价?

一句话结论

DP 把递归展开成状态表,每个状态只计算一次,时间 = 状态总数 × 单状态枚举转移的代价;空间 = 状态表大小。

概念解释

  • 状态:DP 表的一个条目。
  • 转移:从前驱状态推当前状态的选择循环。
  • 无后效性:当前状态决定未来,不受路径影响。

原理流程

  1. 确定状态维度与取值范围。
  2. 统计状态总数。
  3. 单状态看转移循环长度。
  4. 相乘得时间,表长得空间。

代码 / 示例

最长递增子序列:状态 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);若仍用手动栈模拟,空间与原递归深度同阶。

概念解释

  • 直接迭代:状态用变量保存,无栈。
  • 手动栈:把栈帧内容压入显式容器,空间等价递归。
  • 记忆化表在迭代版本中仍保留。

原理流程

  1. 判断能否用变量递推(尾递归、线性递推)。
  2. 不能则用显式栈保存待处理节点。
  3. 统计容器最大占用。

代码 / 示例

// 迭代斐波那契: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!)。

概念解释

  • 分支数与收缩比例共同决定量级。
  • 叶节点数与层代价谁主导看主定理情形。

原理流程

  1. 识别 a(分支数)与 b(收缩比)。
  2. 对照递推形式查表。
  3. 特殊枚举形式单独标注。

代码 / 图示

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 递推式分析时容易漏掉什么代价?

一句话结论

容易漏掉:递归外的扫描/合并、哈希表与临时数组、递归栈空间、字符串与集合拷贝;分析时必须把这些并入对应层代价。

概念解释

  • 层内工作:除调用外的循环、查找、拷贝。
  • 附加结构:缓存表、临时数组。
  • 栈空间:单独统计,不混入时间。

原理流程

  1. 逐行标注非递归语句代价。
  2. 识别新建容器及其规模。
  3. 时间递推式与空间清单分别成文。

代码 / 图示

易漏清单:
合并段扫描 O(n)
排序子数组 O(n log n)
临时拷贝 O(n)
递归栈 O(h)

常见误区

  • 误区:递推式只写递归调用项;正解:当前层工作 f(n) 必须写全。
  • 误区:空间只看 new 出来的对象;正解:调用栈、迭代器、临时引用都要盘点。

追问

  • Q:递归中用了全局缓存表,空间怎么算? A:缓存表按状态数 O(状态数),另加递归栈 O(h)。
  • Q:合并里用了排序? A:把排序代价写进 f(n),整体重新评估量级。