DSA MASTERY · CURRICULUM

Ch.12

分治与递归

建立递归定义、问题分解、合并结果与复杂度分析框架。

draft · 草稿

学习目标

用函数契约、基本情况和规模度量建立可终止的递归模型
从题意提炼 Divide–Conquer–Combine 并判断子问题独立性
用合并不变量解决排序、结构构造与跨区间计数问题
用归纳法、递归树和主定理验证正确性与复杂度

从递归合同到可证明的分治

12.1 函数契约、调用栈、边界与规模递减
12.2 自相似结构、均衡拆分与单侧递归
12.3 有序归并、结构拼装、结果组合与跨区间计数
12.4 终止性、归纳证明、递推式与方法边界

已有内容入口

第 12 章：从自相似问题到分治框架章节导读 递归建模：函数契约、边界与规模递减理论文章 递与归：调用栈、递归树和迭代改写理论文章 分治建模：Divide–Conquer–Combine理论文章 合并答案：分治算法真正困难的部分理论文章 递归算法的终止性与正确性证明理论文章 从递推式到复杂度：递归树与主定理理论文章 方法选择：递归、分治、迭代、DP 与回溯理论文章 Lab 12-E-01：Function相关 Lab Lab 12-E-02：幂次方相关 Lab Lab 12-E-03：南蛮图腾相关 Lab Lab 12-E-04：Pow(x, n)相关 Lab Lab 12-E-05：赦免战俘相关 Lab Lab 12-E-06：Secret Cow Code相关 Lab Lab 12-E-07：求第 k 小的数相关 Lab Lab 12-E-08：Sort an Array相关 Lab Lab 12-E-09：Construct Quad Tree相关 Lab Lab 12-E-10：地毯填补问题相关 Lab Lab 12-E-11：逆序对相关 Lab Lab 12-E-12：Different Ways to Add Parentheses相关 Lab Lab 12-E-13：Beautiful Array相关 Lab Lab 12-E-14：Reverse Pairs相关 Lab Lab 12-E-15：Count of Smaller Numbers After Self相关 Lab Lab 12-E-16：Count of Range Sum相关 Lab