定义
将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
每一次递归都会涉及三个操作
- 分解：将原问题分解成一系列子问题；
- 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
- 合并：将子问题的结果合并成原问题；
使用分治算法的前提条件
- 原问题与分解成的小问题具有相同的模式；
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
- 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
- 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
分治算法实践
- 如何编程求出一组数据的有序对个数或者逆序对个数呢？
解答：使用归并排序算法
public class MergeSort {
private int num = 0;
public int count(int[] a, int n) {
num = 0;
mergeSortCount(a, 0, n - 1);
return num;
}
private void mergeSortCount(int[] a, int p, int r) {
if (p >= r) {
return;
}
int q = (p + r) / 2;
mergeSortCount(a, p, q);
mergeSortCount(a, q + 1, r);
merge(a, p, q, r);
}
private void merge(int[] a, int low, int middle, int high) {
int i = low;
int j = middle + 1;
int k = 0;
int[] tmp = new int[high - low + 1];
while (i <= middle && j <= high) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
}
else {
num += (middle - i + 1); //统计middle-low之间，比a[j]大的元素个数
tmp[k++] = a[j++];
}
}
while (i <= low) {
tmp[k++] = a[i++];
}
while (j <= high) {
tmp[k++] = a[j++];
}
for (i = 0; i <= high - low; ++i) {
a[low + i] = tmp[i];
}
}
}
二位平面上有n个点，如何快速计算出两个距离最近的点对？
解答：分成两块单独求其中一块点对最小距离，然后求这两块之间点对的最小距离，通过一些排序和删除，可以减少到6个点之间比较。有两个nn的矩阵A，B，如何快速求解两个矩阵的乘积C=AB?
解答：v.斯特拉森提出了2*2分块矩阵的计算公式 从原来的8次乘法 缩减到了7次
当n规模很大的时候 缩减效果就很明显 （7/8）^(logn)给10GB的订单文件按照金额排序？
解答：我们先扫描一遍订单，根据订单的金额，将10GB的文件划分为几个金额区间。为什么说MapReduce的本质就是分治思想？
解答：MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理处理器。它从GFS中拿数据，交给Borg中的机器执行，并且时刻监控机器执行的速度，一旦出现机器宕机、进度卡壳等，就重新从Borg中调度一台机器执行。
典型的应用场景
- 用来指导编码，降低问题求解的时间复杂度
- 解决海量数据处理问题
解释
Google文件系统（英语：Google File System，缩写为GFS或GoogleFS），一种专有分布式文件系统，由Google公司开发，运行于Linux平台上
BigTable是一种压缩的、高性能的、高可扩展性的，基于Google文件系统（Google File System，GFS）的数据存储系统，用于存储大规模结构化数据，适用于云端计算
MapReduce是Google提出的一个软件架构,用于大规模数据集（大于1TB的并行运算)。
创新并非离我们很远，创新的源泉来自对事物本质的认识。无数优秀架构设计的思想来源都是基础的数据结构和算法，这本身就是算法的一个魅力所在。
