分治法

概述

分治法（Divide and Conquer）是一种将原问题分解为若干个规模较小的独立子问题，递归求解后再将子问题的解合并为原问题解的算法设计策略。其核心三步为：分解（Divide）→ 解决（Conquer）→ 合并（Combine）。分治法是许多高效算法的基础，其时间复杂度通常由递推关系刻画，可用主定理求解。

定义

分治法（Divide and Conquer）

分治法是一种递归式的算法设计范式，包含三个步骤：

1. 分解（Divide）：将原问题划分为若干个规模更小的子问题，子问题之间相互独立
2. 解决（Conquer）：递归地求解各子问题。若子问题规模足够小，则直接求解（基本情况）
3. 合并（Combine）：将子问题的解组合成原问题的解

形式化地，若分解产生 $a$ 个规模为 $n/b$ 的子问题，合并代价为 $f(n)$，则运行时间满足递推关系：

$T(n)=aT(n/b)+f(n)$

核心性质

性质	描述	备注
子问题独立性	各子问题之间互不重叠	这是分治法与动态规划的关键区别
递归求解	通过递归调用自身解决子问题	需要明确的递归终止条件
合并步骤	子问题的解需要合并为原问题的解	合并代价 $f(n)$ 影响总复杂度
自然并行性	独立子问题可并行求解	适合动态多线程并行化
平衡分解	子问题规模大致相等时效率最高	不平衡分解可能导致退化

应用场景

分治法在算法导论中有大量经典应用：

• 归并排序：$T(n)=2T(n/2)+\Theta (n)=\Theta (n\log n)$
• 快速排序：$T(n)=T(q)+T(n-q-1)+\Theta (n)$，期望 $\Theta (n\log n)$
• Strassen 矩阵乘法：$T(n)=7T(n/2)+\Theta (n^2)=O(n^{\lg 7})$
• 二分搜索：$T(n)=T(n/2)+\Theta (1)=\Theta (\log n)$
• FFT 多项式乘法：$T(n)=2T(n/2)+\Theta (n)=\Theta (n\log n)$
• 最大子数组问题：$T(n)=2T(n/2)+\Theta (n)=\Theta (n\log n)$

分治法 vs 动态规划

比较维度	分治法	动态规划
子问题关系	子问题不重叠	子问题重叠
求解方式	递归（自顶向下）	自底向上填表或记忆化搜索
存储需求	通常不需要额外存储	需要表格存储子问题解
典型应用	归并排序、Strassen	LCS、矩阵链乘法

参见

• 动态规划 — 子问题重叠时的优化策略
• 主定理 — 求解分治递推关系的核心工具
• 递归关系式 — 描述分治算法运行时间的数学方程
• 递归树 — 分析递推关系的可视化工具
• 归并排序 — 分治法的经典应用
• 快速排序 — 分治法的另一经典应用
• Strassen算法 — 分治法在矩阵乘法中的突破
• 多项式乘法 — FFT 加速多项式乘法
• 动态多线程 — 分治法的并行化