上次给大家带来了分治法的基本介绍和基本思想，今天我们继续来看分治算法的几个经典例子。
**01 **
快速排序
image
1.1 背景介绍
上一篇文章里给大家介绍了归并排序，今天首先给大家带来同样运用分治法来解决问题的快速排序。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.2 思路分析
总体思路： 分而治之。
具体操作：选中一个元素为枢轴，以这个枢轴为参照，和每个元素相比较，通过交换位置，将比该枢轴大的元素放在数组尾部，比该枢轴小的元素放在数组头部。当已这个枢轴重新排序出来之后，数组分为三个部分，小于枢轴数组，枢轴，大于枢轴数据，这时，分而治之，小于枢轴数组，大于枢轴数组分别再递归调用，即可完成排序。
伪代码如下：
QuickSort(A,p,r) if p<r
q = Partition(A,p,r) //确定划分位置
QuickSort(A,p,q-1) //子数组A[p...q-1]
QuickSort(Q,q+1,r) //子数组A[q+1...r] 快速排序关键过程是对数组进行划分，划分过程需要选择一个枢轴（pivot element）作为参照，围绕着这个枢轴进划分子数组
Partition(A,p,r) //p、r为数组下标
x = A[r] //将最后一个元素作为主元素
i = p-1 // i指向的是比主元素小的位置，
for j = p to r-1 //从第一个元素开始到倒数第二个元素结束，比较确定主元素的位置
do if A[j] <= x then i = i+1 //如果比主元素小，则把i=i+1的位置上的元素和j位置发现小元素互换
exchange A[i] <-> A[j]
exchange A[i+1]<->A[r] //最终确定主元的位置
return i+1 //返回主元的位置
**02 **
大整数乘法
2.1 背景介绍
在计算机中，长整形（long int）变量的范围是-2147483648至2147483647，因此若用长整形变量做乘法运算，乘积最多不能超过10位数。即便用双精度（double）变量，也仅能保证16位有效数字的精度。所以需要用算法来解决大整数相乘的问题。
2.2 思路分析
问题的关键如下：
image
image
利用公式可将问题转化为递归的形式并加以解决。
03
Strassen矩阵算法
3.1 背景介绍
矩阵乘法是种极其耗时的运算。
以C = A • B为例，其中A和B都是 n x n 的矩阵。根据矩阵乘法的定义，计算过程如下：
//矩阵乘法，3个for循环搞定 void Mul(int** matrixA, int** matrixB, int** matrixC) { for(int i = 0; i < 2; ++i) { for(int j = 0; j < 2; ++j) { matrixC[i][j] = 0; for(int k = 0; k < 2; ++k) { matrixC[i][j] += matrixA[i][k] * matrixB[k][j]; } } } }
由于存在三层循环，它的时间复杂度将达到O(n3)。
下面介绍Strassen算法，该算法将时间复杂度降低到O(nlg7) ≈ O(n2.81)。
3.2 思路分析
Strassen算法是一种基于分治策略的改进算法，我们先来看下简单的分治算法。
image
经计算可以看到，分治策略改进的矩阵计算并不能降低时间复杂度。要想提高算法效率，由主定理方法可知必须想办法将2中递归式中的系数8减少。Strassen算法就是基于此进行了改进。
如图所示：
image
image
Strassen用了更多的步骤，成功的把计算量变成了7个矩阵乘法和18个矩阵加法。虽然矩阵加法增加了好几倍，而矩阵乘法只减小了1个，但在数量级面前，18个加法仍然渐进快于1个乘法。这就是该算法的精妙之处。
**04 **
棋盘覆盖问题
4.1 背景介绍
在一个2^k * 2^k个方格组成的棋盘中，有一个方格与其它的不同，若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格，如何覆盖。四个L型骨牌如下图：
image
特殊的方格位置如下：
image
4.2 思路分析
可以用数学归纳法证明一定有解。
下面来用分治的思想解决问题。
1.当k>0时，将2k2k棋盘分隔称为4个2(k-1)2(k-1)子棋盘。
2.特殊的方格肯定在这4个较小的棋盘中，其余3个子棋盘肯定没有特殊方格。用一个L方格覆盖这3个子棋盘的汇合处。
3.这3个子棋盘被覆盖L形骨牌就成了3个有特殊方格的棋盘，然后递归求解，直至转化2*2棋盘。
**05 **
线性时间选择问题
5.1 背景介绍
从数组中选择第i小的数，并且要求问题的渐近时间复杂度为O(n)。
5.2 思路分析
线性时间选择随机划分法可以模仿随机化快速排序算法设计。对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理，用一个随机的序列中的数作为枢纽，用快速排序算法，进行一次快排，然后将枢纽值和k值进行比较，以此来确定k值。
性能：平均O（n） 最坏O(n^2)
伪代码如下：
5.3 code time
06
最接近点对问题
6.1 背景介绍
给定直线上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
6.2 思路分析
最基本的思路我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n^2)的计算时间。
下面分析分治法：
image
考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。
如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对，类似之前的最大子序列问题。
通过观察发现，当合并时，最小的一定是前一个序列的最大和后一个序列的最小点。
可用分治法解决。
6.3 code time
//参考自https://blog.csdn.net/liufeng_king/article/details/8484284#include<bits/stddc++.h>using namespace std;const int maxn=100005;struct Point{ double x;}p[maxn];int a[maxn];int cmpx(Point a,Point b){ return a.x<b.x;}inline double dis(Point a,Point b){ if(a.x>b.x) return a.x-b.x; else return b.x-a.x;}double closest(int low,int high){ if(low+1==high) //只有两个点 return dis(p[low],p[high]); if(low+2==high) //只有三个点 return min(dis(p[low],p[high]),min(dis(p[low],p[low+1]),dis(p[low+1],p[high]))); int mid=(low+high)/2; //求中点即左右子集的分界线 double d=min(closest(low,mid),closest(mid+1,high)); d=min(d,dis(p[mid],p[mid+1])); //最后一步，合并 return d;}int main(){ int n; while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++) scanf("%lf",&p[i].x); sort(p,p+n,cmpx); printf("%.2lf\n",closest(0 , n-1));//最近点对间的距离 } return 0;
**07 **
循环赛日程表问题
7.1 背景介绍
设有n(n=2^k)支队伍參加循环赛，循环赛共进行n-1天，每支队伍要与其它n-1支队伍比赛一场，且每支队伍每天必须比赛一场，不能轮空。试按此要求为比赛安排日程。
7.2 思路分析
基本思路是按分治策略，我将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手。
我们来看具体的实现。
我们先安排奇数下标位置与偶数下标位置之间的比赛，全部奇数号组成一个序列[1,3...n-1]，以奇数组[1,3,5,7]为例，接下来，再将队伍一分为二，得到[15],[37],此时已不可再分出子队伍，计算结束。
**08 **
总结
可以看到，虽然问题很多种多样，但共同点都是划分子问题，利用计算机的递归求解，最后合并问题。
分治，是一种思想。希望大家不论是在设计程序，或是平常生活中都能利用上这种思想，成为更好的算法master！
image
有问题欢迎交流，作者邮箱1642940680@qq.com
网友评论