分治算法
分治（Divide and Conquer）是算法设计中最具代表性的通用方法论之一——它不是某一个具体算法，而是一套把原问题拆成若干规模更小的同构子问题、递归求解后再合并子问题的解得到原问题解的思想。其核心抓住三个动作：**分解（Divide）**把问题切成规模相近的子问题、**解决（Conquer）递归地求解子问题（足够小时直接算）、合并（Combine）把子问题的解拼装成原问题的解。只要一个问题能被自然地切分成相互独立、结构相同的子问题，分治就能把「处理 n 个元素的代价」分解成一棵递归树，再借助主定理（Master Theorem）**精确算出总代价——典型如归并排序 T(n)=2T(n/2)+O(n)=O(n log n)、快速排序、二分查找（减治特例）。
分治的全部考点都源于一个心智模型：「子问题独立同构 + 递归树 + 合并代价」。由此衍生出三大主题：①分治三步与主定理（分/治/合三步、递推关系 T(n)=aT(n/b)+f(n)、主定理三种情况比较 n^(log_b a) 与 f(n)）；②经典分治应用（归并排序、快速排序、二分查找、最近点对、大整数乘法 Karatsuba、矩阵乘法 Strassen）；③分治与 DP/贪心的辨析（分治子问题独立、DP 子问题重叠、贪心强调局部最优即全局最优）。其中主定理是分析一切分治复杂度的「公式」，归并排序是分治范式的教科书范例，最近点对展示了分治在几何问题上的威力，Strassen 矩阵乘法与 Karatsuba 大整数乘法则是分治突破朴素下界的经典——它们本质都是「分 + 合的代价能否被优化」的反复实践。本叶是高级算法的开篇，吃透分治三步、主定理与辨析，后续 DP、回溯、减治才有比照的根基。
评价
优点
- 化繁为简：把规模为 n 的大问题切成对数深度的递归树，每层只处理「同构但更小」的子问题——代码结构清晰、可读性强，递归实现通常非常简洁
- 天然并行：子问题相互独立，可分布到多核/多机并行求解（分治是并行计算与 MapReduce 的理论基础）
- 复杂度可分析：主定理给出
T(n)=aT(n/b)+f(n)的闭式解，绝大多数分治算法的复杂度可直接套公式得出，无需手画递归树 - 突破朴素下界：分治是优化乘法类问题（Strassen 矩阵乘法 O(n^2.81) 优于朴素 O(n³)、Karatsuba 大整数乘法 O(n^1.585) 优于朴素 O(n²)）的核心武器
缺点
- 递归栈开销：递归实现带来函数调用与栈空间成本，深度大时可能栈溢出；实际工程常需改成迭代（如快排改循环、二分天然迭代）
- 子问题必须独立：若子问题之间重叠（如朴素递归求斐波那契），分治会指数级重复计算——此时必须升级为 DP（加记忆化/递推填表）消去重叠
- 合并代价是关键：分治的总复杂度由「分解代价 + 子问题代价 + 合并代价」共同决定，合并步骤若做不好（如朴素合并），整个算法可能退化到与暴力无异
- 常数因子偏大：分治的递归与合并带来的常数开销，在小规模数据上常不如简单的直接算法（这也是为什么快排/归并会设「小数组切插入排序」的阈值）
本叶地图
- 入门 —— 分治是什么、分治三步、适用条件（子问题独立同构）、分治 vs DP、分治 vs 贪心
- 分治三步与主定理 —— 分/治/合详解、递推关系
T(n)=aT(n/b)+f(n)、主定理三种情况、用主定理分析归并/快排/二分、分治代码模板 - 经典分治应用 —— 归并排序、快速排序、二分查找（减治特例）、最近点对、Karatsuba 大整数乘法、Strassen 矩阵乘法、求众数
- 参考 —— 主定理三种情况表、经典应用复杂度表、分治代码模板、分治 vs DP、易错点清单
交互演示
分治无专门交互演示，建议结合归并排序与快速排序可视化理解分治过程。