思想

递归

分治的条件

1. 规模缩小到一定程度可以容易解决
2. 具有最优子结构性质
3. 子问题的解可以合并为该问题的解（与动态规划的区别）（不能：贪心、DP）
4. 不包含公共子问题（各个子问题相互独立，否则使用DP） 快速排序：原地排序、$nlogn$

2.3 二分搜索

2.4 大整数乘法

2.5 Strassen矩阵乘法

2.7 合并排序

2.8 快速排序

2.9 选择问题

长度为$n$线性有序集合，找出第$k$小 分治，$pivot$ 线性时间选择问题，问题规模 $0<\epsilon<1$

步骤

1. 划分成$\frac{n}{5}$个组
2. 各组内任意排序
3. 每组中，$pivot_{i}$ = 中位数
4. 一共$\frac{n}{5}$个$pivot$，再找出中位数 只有75个元素以上才能缩小$\frac{1}{4}$

补充

划分因子选择3、7：7可以，3不行

2.10 最近点对问题

直线

暴力$O(n^{2})$ 一次排序、一维扫描，$O(nlogn)$

二维

蛮力；分治（平衡子问题） 如何分治？能在线性时间内完成？