一、什么是分治
【百度百科】分治法（(Divide and Conquer)）可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
分治法的精髓：
1、 分--将问题分解为规模更小的子问题；
2、 治--将这些规模更小的子问题逐个击破；
3、 合--将已解决的子问题合并，最终得出“母”问题的解；
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
大白话：大事化小，小事化了。
二、分治法能解决的问题特征
1、 该问题的规模缩小到一定的程度就可以容易地解决；
2、 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
3、 利用该问题分解出的子问题的解可以合并为该问题的解；
4、 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
大白话：简单问题分治法，复杂问题贪心法或动态规划，是否简单看上面的四个特征↑。
PS:大数据中运用分治法非常多，通常会把大问题分解成相同的小问题，后面我们再慢慢聊。
三、分治法解法
由分治法产生的子问题往往是原问题的较小模式，这就可以使用递归技术来解决。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
这样，我们就把分治法化为了怎么进行递归。
1.求解递归式的三种方法
这三种方法分别是：代入法，递归树法，和主方法。代入法是一种十分强大的方法，它几乎可以求解所有的递归式。然而，对于一些“小鸡”来说，不需要这么强大的“牛刀”。对于一些特定类型的递归式（具体类型在主方法的小节中会介绍），用主方法可以用更少的时间得到一个更确切的界。
2.分治法在每一层递归上都有三个步骤：
1、 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2、 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
3、 合并：将各个子问题的解合并为原问题的解；
3.它的一般的算法设计模式如下：
1、 1.if|P|≤n0；
2、 2.thenreturn(ADHOC(P))；
3、 3.将P分解为较小的子问题P1,P2,...,Pk；
4、 4.fori←1tok；
5、 5.doyi←Divide-and-Conquer(Pi)△递归解决Pi；
6、 6.T←MERGE(y1,y2,...,yk)△合并子问题；
7、 7.return(T)；
四、分治法实现最近对问题（JAVA）
题目：假设所有点都在集合S中。
1、 用S中个点坐标的中位数作为分割点，则会得到一个平衡的分割点m，使得子集S1,S2中有个数大致相同的点；
2、 选取垂直线x=c（中位线）来作为分割线；
3、 递归地求出S1和S2中的最近对，假设D1、D2是最近距离；
4、 距离最近的点，可能在线的俩边，所以，我们需要在以x=c为对称的、宽度为2D的（D为D1、D2中的最小值）的垂直带中；
5、 在该范围中递归得出最近距离；
import java.util.*;
public class S2_4 {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int x=0,x1=0,x2=0,x3=0,x4=0;
int y=0,y1=0,y2=0;
double dis1=0,dis2=0;
System.out.print("输入需要生成多少个随机点N：");
int n=s.nextInt();
int A[][]=new int[n][2];
int B[][]=new int[n][2];
int C[][]=new int[n][2];
int D[][]=new int[n][2];
for(int i=0;i<n;i++) {
A[i][0]=(int)(Math.random()*100)+1;//生成100以内的随机数,放入横坐标
}
for(int i=0;i<n;i++) {
A[i][1]=(int)(Math.random()*100)+1;//生成100以内的随机数,放入纵坐标
}
for(int i=0;i<n;i++) {
System.out.println("("+A[i][0]+","+A[i][1]+")");
}
int minX = (int) Double.POSITIVE_INFINITY; //保证假设的初始最小值足够大
int maxX = (int) Double.NEGATIVE_INFINITY; //保证假设的初始最大值足够小
for(int i = 0; i < A.length; i++){
if(A[i][0] < minX)
minX = A[i][0];
if(A[i][0] > maxX)
maxX = A[i][0];
}
int mid = (minX + maxX)/2;
int p=0,t=0;
for(int i=0;i<n;i++) { //将x坐标分成俩个部分
if(A[i][0]<=mid) {
B[p][0]=A[i][0];
B[p][1]=A[i][1];
p++;
}
else {
C[t][0]=A[i][0];
C[t][1]=A[i][1];
t++;
}
}
int d1=(int) Double.POSITIVE_INFINITY,d2=(int) Double.POSITIVE_INFINITY; //设置俩边的距离最小值为较大的数值
int dx=0,dy=0,dz=0;
for(int i=0;i<=p-2;i++) //得出d1的值
for(int j=i+1;j<=p-1;j++) {
dx=(B[j][0]-B[i][0])*(B[j][0]-B[i][0])+(B[j][1]-B[i][1])*(B[j][1]-B[i][1]);
if(dx<d1) {
d1=dx;
x1=i; //记录俩个点的坐标
x2=j;
}
}
for(int i=0;i<=t-2;i++) //得出d2的值
for(int j=i+1;j<=t-1;j++) {
dy=(C[j][0]-C[i][0])*(C[j][0]-C[i][0])+(C[j][1]-C[i][1])*(C[j][1]-C[i][1]);
if(dy<d2) {
d2=dy;
x3=i; //记录俩个点的坐标
x4=j;
}
}
System.out.println("mid="+mid+" "+"d1="+d1+" "+"d2="+d2);
if(d1<d2) {
dz=d1;
dis1=Math.sqrt(dz);
System.out.println("x坐标中的最小距离的俩个点为："+A[x1][0]+","+A[x1][1]+" "+A[x2][0]+","+A[x2][1]);
System.out.println("最小距离为："+dis1);
x=x1;
y=x2;
}else {
dz=d2;
dis1=Math.sqrt(dz);
System.out.println("x坐标中的最小距离的俩个点为："+A[x3][0]+","+A[x3][1]+" "+A[x4][0]+","+A[x4][1]);
System.out.println("最小距离为："+dis1);
x=x3;
y=x4;
}
int q=0;
for(int i=0;i<n;i++) {
if((mid-dis1)<=A[i][0] && A[i][0]<=(mid+dis1)) { //中心线左右俩边的最小距离内寻找俩边的最近点
D[q][0]=A[i][0];
D[q][1]=A[i][1];
q++;
}
}
double mind=Double.POSITIVE_INFINITY;//mind设置为正无穷大，作为比较值
double dis=0;
for(int k=0;k<=q-2;k++)
for(int j=k+1;j<=q-1;j++) {
dis=(D[j][0]-D[k][0])*(D[j][0]-D[k][0])+(D[j][1]-D[k][1])*(D[j][1]-D[k][1]);
if(dis<mind) {
mind=dis;
y1=k; //记录俩个点的坐标
y2=j;
}
}
dis2=Math.sqrt(mind);
System.out.println("dis1="+dis1+" "+"dis2="+dis2);
if(dis1<dis2) {
System.out.println("最小距离为："+dis1);
System.out.print("俩个点分别为："+"("+A[x][0]+","+A[x][1]+")");
System.out.println(" "+"("+A[y][0]+","+A[y][1]+")" );
}else {
System.out.println("最小距离为："+dis2);
System.out.print("俩个点分别为："+"("+A[y1][0]+","+A[y1][1]+")");
System.out.println(" "+"("+A[y2][0]+","+A[y2][1]+")" );
}
}
}
五、经典问题
1、 二分搜索[1]；
2、 大整数乘法；
3、 Strassen矩阵乘法；
4、 棋盘覆盖；
5、 合并排序；
6、 快速排序；
7、 线性时间选择；
8、 最接近点对问题；
9、 循环赛日程表；
10、 汉诺塔；
11、 大数据；
我的微信公众号：架构真经（id：gentoo666），分享Java干货，高并发编程，热门技术教程，微服务及分布式技术，架构设计，区块链技术，人工智能，大数据，Java面试题，以及前沿热门资讯等。每日更新哦！
参考资料：
1、 https://blog.csdn.net/xlinsist/article/details/79198842；
2、 https://blog.csdn.net/weixin_42059543/article/details/83001863；
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: