跳至主要內容

递归与分治

周子力大约 10 分钟教学文档算法设计与分析递归分治法专题导学

递归与分治

递归描述函数怎样调用自身,分治描述问题怎样分解、求解与合并。本专题从函数任务和返回值出发,串联数值汇总、字符串处理、树构造、排序计数、空间划分及代数计算。新增十题按简单、中等、中高难度和高难度递进;各题的完整代码、执行过程和练习集中在独立题目文档中。

从递归任务到分治结构

设计递归函数时,先说明一次调用负责什么任务,再给出能够直接处理的边界,并保证每次子调用都会接近边界。

例如猴子吃桃每次把剩余天数减少1,汉诺塔把移动圆盘的任务交给两个规模更小、柱子角色不同的子任务。调用次数、调用深度与输出量需要分别分析;使用递归本身不保证高效。

分治通常将原问题分解成若干较小的同类子问题,求出它们的结果,再合成为当前答案。分析时应明确:

  1. 分解后是否覆盖原问题,是否遗漏或重复处理元素?
  2. 子调用的输入与返回值是什么,两个子任务是否真的需要分别求解?
  3. 当前层凭什么能从子问题结果得到正确答案?
  4. 子问题是否严格变小,边界能否正确处理?

子任务的执行顺序还要服从题目约束。汉诺塔必须按顺序执行两个移动任务;排序和下面的基础题则分别汇总左右位置区间的结果。

快速幂按幂的性质分解表达式后,只求一次半次幂并复用结果。按广义分治讲解,它体现“分解、求解、合成”;按一次只进入一个更小子问题的分类,它也具有减半减治结构。分析复杂度时,应按实际执行的一次子调用计费。

分治基础 三种返回值

建议按以下顺序学习,重点比较返回值设计与合并工作量:

学习顺序题目子调用返回什么当前层怎样合并或连接
1同时求数组的最大值与最小值两个极值分别比较两侧的最小值和最大值
2最长公共前缀一组字符串的公共前缀从首字符开始合并两个前缀
3有序数组构造平衡二叉搜索树一棵子树的根节点创建当前根,连接左右子树

第一题训练固定大小摘要的汇总;第二题的摘要长度可变,合并需要字符比较;第三题直接构造一种数据结构,结果是节点及其连接关系。

这三题都按中点划分,但需要检查的边界不同:极值题拒绝空列表,公共前缀题对空列表返回空字符串,树构造对空区间返回 None。边界应由任务含义决定。

从基础题进入合并、空间与代数专题

合并与统计

合并排序分别求解左右排序子问题,再线性合并有序列表。逆序对沿用这个结构,在取出右侧较小元素时,批量统计它与左侧剩余元素的配对。

学习路线为:最大最小值的常数工作合并 → 合并排序的线性合并 → 逆序对的排序与计数合并。算法中出现两次规模减半的子调用时,总时间还取决于当前层的额外工作。

合并k个有序数组(中等)把线性归并推广到多个已有序输入,通过按数组个数均衡划分,控制每个元素经历的合并层数。

重要逆序对(中高难度)沿用普通逆序对的三类位置划分,但条件变为 ai>2aja_i>2a_j。排序与配对判断需要分开,当前层先用单调双指针计数,再合并列表;不能直接复用普通逆序对的取元素计数规则。

快速排序、数组中第k个最大元素和两个有序数组的中位数可用于进一步比较分区、选择与缩小候选范围的规则。

构造与空间划分

平衡搜索树通过中点划分构造左右子树;棋盘覆盖把空间分成四个区域,并通过当前层的骨牌安排,使子区域满足同类问题的条件。循环赛日程表则用较小规模的安排构造整体赛程。

对构造题,除了证明结果合法,还需计算输出本身的规模。返回一棵含 nn 个节点的树,需要线性的节点存储,即使递归栈只有对数深度。

四叉树构建与二值图像压缩(中等)在区域一致时停止,否则四分。它用前缀和避免重复扫描区域,输出树的大小随图像结构变化,完整预处理仍需访问全部像素。

二维有序矩阵查找(中等)在中间列确定分界行,排除左上、右下区域,再递归查找左下、右上。先证明哪些位置可以排除,才能确定正确的子问题范围。

平面最近点对(高难度)按横向位置均衡划分,合并时必须检查跨侧点对。几何约束把条带中每个点的候选限制为常数个;子调用还返回纵向顺序,避免每层重新排序。这是“先证明合并工作量,再实现分治”的进阶实例。

用代数关系减少乘法分支

从快速幂的结果复用出发,继续学习 Karatsuba大整数乘法和 Strassen矩阵乘法(均为高难度)。前者把四个半长乘法改为三个,后者把八个半阶矩阵乘法改为七个;增加的加减工作必须与减少的乘法一起计费。

两题可按“展开原公式 → 构造较少的子乘积 → 重组并验证 → 分析递推”学习。整数乘法的规模是位数,矩阵乘法的规模是阶数;减少递归分支能降低渐近指数,但不能由此断言教学实现对所有小输入都更快。

递推与候选排除

约瑟夫环通过较小圆环的答案及编号映射构造当前答案;木材加工依靠可切段数的单调性二分候选长度;费解的开关枚举第一行的按法,再逐行唯一确定后续操作。

这些题目共同训练“利用结构减少工作”,具体依据分别是编号关系、单调性和状态约束。应说明各题实际使用的方法,而不是将目录中的全部题目都归为同一种分治算法。

比较复杂度时同时看三个因素

对于均衡划分的典型分治结构,可以用运行时间递推式表示:

T(n)=rT(n/b)+f(n). T(n)=rT(n/b)+f(n).

其中 rr 是实际执行的子调用数量,n/bn/b 是子问题规模,f(n)f(n) 是分解与合并等当前层额外工作。它描述的是时间,不是题目答案的数值递推式;应用时还需要补充边界及不均匀划分的情况。

实例实际子调用当前层工作时间结论
快速幂一次,指数约减半常数次算术操作单位成本模型下 O(log⁡(n+2))O(\log(n+2))
最大最小值两次,区间约减半常数次极值比较O(n)O(n)
最长公共前缀两次,字符串个数约减半比较并生成两个前缀的公共部分上界 O(n(ℓ+1))O(n(\ell+1)),ℓ\ell 为最长字符串长度
平衡搜索树构造两次,选根后分成左右区间创建一个节点并连接子树非空输入 O(n)O(n)
合并排序与逆序对两次,元素个数约减半线性合并或归并计数至少两个元素时 O(nlog⁡n)O(n\log n)
合并k个有序数组两次,数组个数约减半合并两组有序结果O(k+Nlog⁡(k+1))O(k+N\log(k+1)),NN 为总元素数
二维有序矩阵查找至多两次,列数约减半且行范围分开扫描中间列并排除区域非空矩阵上界 O(mlog⁡(n+1))O(m\log(n+1)),m,nm,n 为行列数
四叉树构建非一致区域四次,边长减半用前缀和判断区域并连接四子树含预处理 O(n2)O(n^2),nn 为边长
重要逆序对两次,元素个数约减半双指针计数后线性归并至少两个元素时 O(nlog⁡n)O(n\log n)
平面最近点对两次,点数约减半纵向归并与有限条带候选检查O(nlog⁡n)O(n\log n),含初始排序
Karatsuba大整数乘法三次,位数约减半,和可能多一位线性位数成本的加减与移位按位成本 O(dlog⁡23)O(d^{\log_2 3}),dd 为最大位数
Strassen矩阵乘法七次,补齐矩阵阶数减半矩阵加减与块重组单位标量成本 O(nlog⁡27)O(n^{\log_2 7})

各题中的 nn 表示各自的输入规模。只看递归深度会漏掉其他分支的工作,只看子调用数量又会漏掉合并成本。

空间分析同样要分开考虑调用栈、中间结果与输出。下标区间可以避免复制输入列表,但返回前缀可能创建新字符串,构造树则会创建新节点;具体实现决定哪些存储同时存活。

学习与核对方式

阅读每道题时,先用主示例手画调用关系,再按程序返回顺序核对结果;之后运行文档中的 Python 主实现,并检查空输入、单元素、重复值或奇数长度等适用边界。

新增十题的建议顺序是:三道基础题 → 多路合并与二维查找 → 四叉树 → 重要逆序对 → Karatsuba → 最近点对 → Strassen。进入重要逆序对前先完成普通逆序对;进入最近点对前先掌握合并排序中的有序结果维护。最后横向比较各题的子问题数、合并成本和输出规模。

用题目文档的“易错点”检查自己的理解,再独立完成“课堂练习”后展开参考答案。方法串联可结合2026年秋第4次课,整体分类可参考算法概览。

上次编辑于:
贡献者: zlzhou,molittle,zilizhou