分治法

概述

分治法 是最重要的算法设计范式之一，其核心思想是将原问题分解为若干规模更小的子问题，递归地求解子问题，最后合并子问题的解得到原问题的解。许多高效算法都基于这一策略。

定义

分治法

分治法包含三个步骤：

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

核心性质

• 分治法自然产生递归算法，其运行时间通常由递归关系式刻画。
• 分治法的效率取决于分解策略和合并代价。理想情况下，分解使子问题规模大致相等。
• 分治法是许多经典算法的基础：归并排序、快速排序、Strassen矩阵乘法等。
• 第4章专门讨论分治策略产生的递归关系式的求解方法：代入法、递归树法、主定理等。

章节扩展

第2章：入门

• 2.3 分治法：以归并排序为第一个分治算法示例，引入分治策略的三步范式。

第4章：分治策略

• 4.1 矩阵乘法：分治法应用于矩阵乘法问题。
• 4.2 Strassen算法：通过巧妙的子问题分解将矩阵乘法从 $O(n^3)$ 降至 $O(n^{2.81})$。
• 4.3-4.7：递归关系式的各种求解方法，用于分析分治算法的运行时间。

第7章：快速排序

• 7.1 快速排序的描述 快速排序是分治策略的经典应用：分解(PARTITION)→解决(递归排序两侧)→合并(无需操作)
• 与归并排序的区别：合并阶段不需要额外操作（原地排序），但最坏情况退化为 $\Theta (n^2)$
• 参见：快速排序

第9章：中位数与序统计

• 9.3 最坏情况线性时间选择 SELECT算法使用分治策略：将数组分为 $\lceil n/5\rceil$ 组，递归找中位数的中位数
• 与快速排序/归并排序的区别：只递归一侧或固定大小的子问题
• 参见：BFPRT算法

第23章：所有结点对的最短路径

第23.1节的重复平方技术是分治思想的应用：为计算最短路径权值矩阵的 n 次幂 L^n，使用分治策略 L^n = L^{n/2} · L^{n/2}（当 n 为偶数），将 O(V⁴) 的朴素矩阵乘法优化至 O(V³ lg V)。

参见

• 归并排序
• 递归关系式
• 递归树
• 插入排序