一、 核心范式
1. 三步曲
- 分解
(Divide)：将原问题分解为若干个规模较小、相互独立、形式相同的子问题。
- 解决
(Conquer)：若子问题规模足够小则直接求解，否则递归求解。
- 合并 (Combine)：将子问题的解合并为原问题的解。
2. 通用复杂度模型（主定理
*
*
*
二、 基础经典算法（主定理直接应用）
1. 二分搜索 (Binary Search)
- 逻辑：在有序数组中，每次比较后排除一半元素。
- 方程：
- 参数：
- 分析：
( )，属情况2
- 结论：
2. 大整数乘法 (Large Integer Multiplication)
- 朴素分治：
- 优化分治：利用代数变换将乘法次数降至3次
- 方程：
- 参数：
- 分析：
( )，属情况1
- 结论：
- 方程：
3. Strassen 矩阵乘法
- 朴素分治：
- Strassen
优化：通过线性组合将乘法次数降至7次
- 方程：
- 参数：
- 分析：
( )，属情况1
- 结论：
- 方程：
4. 循环赛日程表 (Round Robin Schedule)
- 核心逻辑：
- 左上角：递归求解的子问题
- 右上角：左上角元素
- 左下角：右上角的对角线镜像
- 右下角：左上角的对角线镜像
- 左上角：递归求解的子问题
- 复杂度：时间
，空间
三、 排序算法（重点对比）
1. 归并排序 (Merge Sort)
- 逻辑：递归拆分 → 有序合并（线性扫描）
- 方程：
- 分析：
，属情况2
- 结论：
- 特点：稳定排序，空间复杂度
（非就地）
2. 快速排序 (Quick Sort)
- 逻辑：选择基准 → 划分分区 → 递归排序
- 最好/平均情况：
- 最坏情况：
（如输入已有序）
- 特点：不稳定，平均性能快，就地排序（栈空间
）
四、 进阶难点（理论证明考点）
1. 线性时间选择：BFPRT 算法
- 问题：在无序数组中找第
小的数
- 对比：
- 随机快选：期望
，最坏
- BFPRT：确定性
- 随机快选：期望
BFPRT 算法步骤（必背）
- 分组：每5个元素一组
- 组内排序：找出每组中位数
- MoM：递归找出“中位数的中位数”作为基准
- 划分：用基准进行划分
时间复杂度证明（核心）
- 递归方程：
：找 MoM 的代价
：处理最坏子问题的代价
- 分析：系数和
，形成收敛几何级数
- 结论：
2. 最接近点对 (Closest Pair of Points)
- 问题：二维平面
个点，找距离最近的一对
- 方程：
- 复杂度：
合并步骤的优化证明（鸽巢原理）
- 窄带筛选：只考虑距离分割线水平距离
的点
- 排序：将窄带内点按
坐标排序（预排序优化）
- 6点定理：
- 对于任意点
，只需检查其后6个点
- 证明：在
矩形内，若超过6个点则必有两点距离 ，与 定义矛盾
- 保证了合并步骤是
而非
- 对于任意点
五、 灵活应用（面试级题目）
1. 两个等长升序数组的中位数
- 思路：比较两个数组的中位数
- 若
，直接返回
- 若
，则解在 Array1 右半部和 Array2 左半部
- 每次丢弃一半，递归求解
- 若
- 复杂度：
2. 寻找缺失的整数（0~100）
- 方法1：求和作差（
）
- 方法2：异或运算（
）
- 方法3：二分查找（如果有序，
）
3. 寻找出现奇数次的数
- 思路：利用异或性质
- 方法：所有元素异或一遍，结果即为所求
- 复杂度：
六、 分治法复习清单
1. 计算能力
- 给定递归式（如
），能快速用主定理算出复杂度
2. 理论证明（重点）
- BFPRT：为什么是
？（关键在于切分比例保证）
- 最接近点对：为什么只需检查6个点？（鸽巢原理）
3. 代码逻辑
- 归并排序的 Merge 过程
- 快速排序的 Partition 过程
4. 算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 二分搜索 | 有序数组查找 | ||
| 大整数乘法 | 3次乘法优化 | ||
| Strassen | 7次乘法优化 | ||
| 归并排序 | 稳定、非就地 | ||
| 快速排序 | 平均 |
不稳定、就地 | |
| BFPRT | 确定性选择 | ||
| 最近点对 | 鸽巢原理优化 |
本章要点：分治法通过“分而治之”将复杂问题分解，关键在于分解策略和合并优化。重点掌握主定理应用、排序算法对比，以及BFPRT和最近点对的理论证明。
如果您喜欢我的文章，可以考虑打赏以支持我继续创作.
