分治思想

什么是分治

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

根据度娘讲解我们知道其本质就是化繁为简，将复杂问题拆分成若干简单问题在进行合并得到复杂问题的最优解。归并排序、快速排序、dp算法等都是分治思想的应用，运用分治思想求解问题，可以大大降低时间复杂度，将其变为O(nlogn)型减少计算。

使用条件

该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题；
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

最后一条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法会做许多重复的不必要的计算工作，重复地解公共的子问题，此时虽然可以使用分治法，但是却并未达到降低时间复杂度的预期效果，所以一般用动态规划更好。

伪代码

divide-and-conquer(P)
{
　if ( | P | <= n0) adhoc(P);   //解决小规模的问题
　divide P into smaller subinstances P1,P2,...,Pk；//分解问题
　for (i=1,i<=k,i++)
　yi=divide-and-conquer(Pi);  //递归的解各子问题
　return merge(y1,...,yk);  //将各子问题的解合并为原问题的解
}

从大量实验发现，在使用分治法设计算法时，最好尽量使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题进行处理，这种时子问题规模大致相等的做法是出自一种平衡子问题的思想，他几乎总是比子问题规模不等的做法要好。

典型例题精讲

找出伪币

现有16个硬币，其中有一个是伪币，并且伪币重量比真币轻。试用一台天平找出这枚伪币。

直接求解：两两比较，最坏情况需要8次找出伪币。

分治法：先分成两堆（各堆8个硬币）称重，然后轻的一堆在分成堆…仅需4次即可找出伪币。

计算a^n的值

直接求解：暴力相乘，时间复杂度为O(n)。

分治法：

k= \begin{cases} n/2,n=even\\ n-1/2,n=odd \end{cases}

a^n=a^k*a^k//分治法思想

所以递归式为T(n)=T(n/2)+O(1)，根据Master定理我们得到logba=0,k=0,所以T(n)=O(logn),时间复杂度降低。

金块问题

有若干金块试用一台天平找出其中最轻和最重的金块,n个数中找出最大和最小的数

直接求解：先找出最大值，然后在剩下的n-1个数中再找出最小值，需要比较2n-3次比较。

直接求解改进：一个数要么是最大值，要么是最小值，所以一个数只需要比较一次即可，这样优化后伪代码如下：

min←a[0];max←a[0];
For i←1 to n-1 do
    if a[i]<min 
            min←a[i]
       else if a[i]>max 
           	max←a[i]

当输入的数组伪排好序时，算法需要2*(n-1)次比较，当输入为逆序时，算法要做n-1次比较，虽然有所较少比较次数，但是时间复杂度认为O(n)，并未改变时间复杂度。

分治法：我们这里使用分治的思想，即将max和min值都设置为arr[0]，然后以2位单位不断拆分直至全部拆分为2个数为一组，然后这两个数中选最大值和最小值，如果恰巧不能完整分组，那么就一个数时既是最大值，也是最小值，然后合并merge时只需要比较每组的最大值和最小值，来选取总数组的最大值和最小值。伪代码如下：

Max-min(A[0,n-1],max,min)
  if n=1 max←min←a[0],return;
  if n=2 {if a[0]≥a[1] max←a[0],min←a[1] 
              else max←a[1],min←a[0];}
      else  m←n/2 
             Max-min(A[0,m-1],max1,min1),
             Max-min(A[m,n-1],max2,min2),
             max←max(max1,max2),
             min←min(min1,min2),
             return.

分析时间复杂度，c(1)=0,c(2)=1,c(n)=2c(n/2)+2,迭代可得c(n)=(3n/2)-2。分治法比直接求解法少用了25%次比较。

上面的伪代码中我们使用了递归调用，但是仔细分析，最终分组的情况无非就是拆成两个相邻的数为一组一个为最大值，一个为最小值，然后从这些最大值和最小值里面寻找最终的最大值解和最小值解，所以我们可以解递归，使用非递归的伪代码实现如下：

template<class T>
bool Max-min(T w[],int n,T& Min,T& Max){
	//寻找w[0:n-1]中的最小和最大值
	//如果少于一个元素，直接退出程序，一个元素就同时为最大值和最小值
	//特殊情况讨论
	if(n<1)return false;
	if(n==1){Min=Max=w[0];return;}
	//多于一个时，先对Min和Max初始化，我们可以初始化为
	Min=0xffff,Max=0;
	int s;//循环起点
	//讨论第一组
	if(n%2){
	//n为奇数
	//先单独把第一个数拿出来当第一组，这样后面就是偶数个了
		Min=Max=w[0];
		s=1;
	}
	else{
	//n为偶数
		if(w[0]>w[1]){
			Min=w[1];
			Max=w[0];
		}
		else{
			Min=w[0];
			Max=w[1];
		}
		s=2;
	}
	//剩下的数对分别比大小
	for(int i=s;i<n;i+=2){
		//寻找w[i]和w[i+1]的较大者
		//较大者和Max比较
		//较小者和Min比较
		if(w[i]>w[i+1]){
			if(w[i]>Max)Max=w[i];
			if(w[i+1]<Min)Min=w[i+1];
		}
		else{
			if(w[i+1]>Max)Max=w[i+1];
			if(w[i]<Min)Min=w[i];
		}
	}
	return true;
}

当n为奇数时，n=2*k+1,比较k对相邻元素，比较次数为3*k=3*(k-1)/2=[3n/2]-2([]表示向上取整)

当n为偶数时，n=2*k，比较k-1对相邻元素，比较次数为1+3*(k-1)=[3n/2]-2(]表示向上取整)

非递归的时间复杂度和递归写分治法的比较次数相同。

大整数的乘法

设计一个有效的算法，可以进行两个n位大整数的乘法运算。

直接求解：第一个数的每一位分别和第二个数的每一位进行相乘然后进位得结果后在相加，时间复杂度较高为O(n^2)。

分治法：

X=A*2^(n/2)+B，Y=C*2^(n/2)+D，所以X*Y=A*C*2^n+(A*D+B*C)*2^(n/2)+B*D

这样时间复杂度为

T(n)=\begin{cases} O(1),n=1\\ 4*T(n/2)+O(n),n>1 \end{cases}

根据Master定理知道T(n)=O(n^2)，虽然使用了分支思想，但是时间复杂度无改进效果，说明分支拆分思路不正确。分析式子知道我们需要减小b值，既减少乘法次数，上式中我们可以看到每次都需要求解AC,AD,BD,BD进行四次乘法计算，所以减少乘法次数，我们对公式进行变形，改为

XY=ac2^n+((a-c)(b-d)+ac+bd)2^{n/2}+bd

或者

XY=ac2^n+((a+c)(b+d)-ac-bd)2^{n/2}+bd

虽然式子看起来较为复杂，但是他们每次只需要进行3次乘法，即ac,bd,(a+c)*(b+d)或者ac,bd,(a-c)*(b-d)，所以时间复杂度为

T(n)=\begin{cases} O(1),n=1\\ 3T(n/2)+O(n),n>1 \end{cases}

根据Master定理知道时间复杂度为O*(n^1.59)，有较大的的优化改进，但是考虑到a+c,b+d可能会得到m+1位的结果有进位问题，所以优先使用(a-c)*(b-d)。

矩阵乘法

两个n×n阶的矩阵A和B的乘积是另一个n×n阶矩阵C，C的元素为

C（i,j)=\sum_{k=1}^{n}{A(i,k)B(k,j)}

那么如果按照直接三重包里循环的话，需要n^3次乘法和n^3-n次加法。代码如下：

template<class T>
void MatrixMulti(T** A,T** B,T** C,int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
        	T sum=0;
        	for(int k=0;k<n;k++){
        		sum+=A[i][k]*B[k][j]
        	}
        	C[i][j]=sum;
        }
    }
}

如果我们对矩阵进行分块合并，即进行分治法思想，每个矩阵分为均匀的四个小得子矩阵，如下图

a,b,c,d是A的四个子矩阵，e,f,g,h是B的四个子矩阵。按照乘法公式计算：

可以得到

T（n)=8T(n/2)+O(n^2)

根据master定理得时间复杂度为O(n^3)，我们发现时间复杂度没有减小，难道是分治法出问题了吗😕？实际上并没有，只是我们分的快太多啦，开销太大啦，经过天才的推理，我们得知分成7块时时间复杂度明显降低（证明就不证了）具体操作如下：

我们将abcdefgh重新按一定规则进行整合，即A，B两个矩阵总共分为7块，此时C的四个子矩阵rstu可以用如下公式计算求解：

例如：r=P5+P4-P2+P6=ae+ah+de+dh+dg-de-ah-bh+bg+bh-dg-dh=ae+bg,经过上面的这种分治拆分，可以得：

T（n)=3T(n/2)+O(n^2)

根据Master定理得时间复杂度为O(n^2.81)明显缩短了。

残缺的棋盘

有一个棋盘，他有一处坏掉了（即下图蓝色方块），你拥有4四个小版块，要用这四个小版块拼成残缺棋盘的样子，坏掉的地方要空出来，即蓝色方块要空出来。

不同情况的残缺棋盘

你拥有的四种小版块

毋庸置疑，残缺的棋盘肯定有某种特定的规律，既然残缺的棋盘总是由这四种小版块拼出，所以我们总是要想方设法将剩余的白色部分拆成许多个小版块，即三个成直角的小白块为一组划分残缺的前，我们不难看出规律。

对于下面这三个复杂的棋盘，每次我们都先填充黄色区域，使得将棋盘分成4个部分后，有残缺块的那个小部分永远没有黄色板块的小方格，这样我们就达到了将白块分割成多个成直角的三个小白块组合了，其实多想一想，有残缺块的部分不能少一个小白格，自然而然拼凑的时候，第一个小版块要避免放在含有残缺块的部分，这样四个部分拥有的小白块才能均匀分布。所以扩展至无限大的棋盘时，思路是一样的，如下：

代码如下：

void TileBoard(int tr, int tc, int dr, int dc, int size){
//覆盖残缺棋盘
	if(size==1)return;//形成不了棋盘
	int t=tile++//所使用的三格板数目
	s=size/2;//象限大小（每个象限长宽为原棋盘的一半）
	//覆盖左上象限
	if(dr<tr+s&&dc<tc+s){
        //残缺方格位于本象限
        //则将三格板t放在右下角
        Board[tr + s - 1][tc + s - 1] = t;
        然后填充剩余部分，即再次划分为4个小版块进行递归调用
        TileBoard(tr,tc,dr+s-1,dc+s-1,s);
	}
	else{
		//如果本象限没有残缺方格
		则直接填充
		TileBoard(tr,tc,dr,dc,s);
	}
	//覆盖右上象限
	if(dr<tr+s&&dc>=tc+s){
        //残缺方格位于本象限
        //则将三格板t放在左下角
        Board[tr + s - 1][tc + s ] = t;
        然后填充剩余部分，即再次划分为4个小版块进行递归调用
        TileBoard(tr,tc+s,tr+s-1,tc+s,s);
	}
	else{
		//如果本象限没有残缺方格
		则直接填充
		TileBoard(tr,tc+s,dr,dc,s);
	}
	//覆盖左下象限
	if(dr>=tr+s&&dc<tc+s){
        //残缺方格位于本象限
        //则将三格板t放在右上角
        Board[tr + s ][tc + s -1] = t;
        然后填充剩余部分，即再次划分为4个小版块进行递归调用
        TileBoard(tr+s,tc,tr+s,tc+s-1,s);
	}
	else{
		//如果本象限没有残缺方格
		则直接填充
		TileBoard(tr+s,tc,dr,dc,s);
	}
	//覆盖右下象限
	if(dr>=tr+s&&dc>=tc+s){
        //残缺方格位于本象限
        //则将三格板t放在右上角
        Board[tr + s ][tc + s ] = t;
        然后填充剩余部分，即再次划分为4个小版块进行递归调用
        TileBoard(tr+s,tc+S,tr+s,tc+s,s);
	}
	else{
		//如果本象限没有残缺方格
		则直接填充
		TileBoard(tr+s,tc+s,dr,dc,s);
	}
}
void OutputBoard(int size){
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++)
            cout<<setw(5)<<Board[i][j];
    }
    cout<<endl;
}

n=4^k,需要(n-1)/3个三格板填满棋盘，算法复杂度

T（n)=4T(n/4)+c

根据Master定理可得时间复杂度为O(n)，时间开销很小。

归并排序

采用平衡分割法分割n个元素，即将n个元素分为A和B两个集合，其中A集合中含有n/k个元素，B中包含剩余的元素，即使拆分尽量均匀，这样效果最好（前面有提到过），然后递归使用分治法对A和B在进行排序，当A和B内元素数少于K时开始进行插入排序，然后在采用一种称为归并(merge)的过程，将已经排序好的A和B合并成一个集合。

知识点补充：插入排序就是最符合人类思维的简单排序方法，第一个元素放进一个空数组后，后面的元素大于最大值，就放后面，小于最小值就放前面。时间复杂度很高，但是当元素很少时，时间开销还是很小的。

例题：考虑8个元素，值分别为[10,4,6,3,8,2,5,7]，我们按k=2进行分治拆分：

1代表拆分后取左半部分，2代表拆分后取右半部分。

A1=[10,4,6,3],A2=[8,2,5,7]
A11=[10,4],A12=[6,3],A21=[8,2],A22=[5,7]
A111=[10],A112=[4],A121=[6],A122=[3],A211=[8],A212=[2],A[221]=[5],A222=[8]
merge1:A11=[4,10],A12=[3,6],A21=[2,8],A22=[5,8]
merge2:A1=[3,4,6,10],A2=[2,5,7,8]
merge3:A=[2,3,4,5,6,7,8,10]

同样可以以k=4进行拆分。

伪代码：

template<class T>
    void sort(T E,int n){
    //对E中的n个元素进行排序，k为全局变量
    if(n>=k){
        //如果传进来的数组数大于k,说明还要继续拆分
        i=n/k;//左半部分
        j=n-i;//剩余部分，因为未必刚好平均分，所以这样取j值
        //令A包含E中的前i个元素
        //令B包含E中余下的j个元素
        sort(A,i);
        sort(B,j);
        merge(A,B,E,I,J);//merge合并
    }
    else{
        //否则就该进行插入排序了
        //使用插入排序对E进行排序
    }
}

递推公式如下：

T(n)=\begin{cases} d,n<k\\ T(n/k)+T(n-n/k)+cn,n>=k \end{cases}

当n/k与n-(n/k)近似相等时，T(n)值最小(Balance原理),所以特别的，当k=2时，分治法具有最佳性能，此时时间复杂度为logn，

T(n)=\begin{cases} d,n<=1\\ T(n/2)+T(n-n/2)+cn=2T(n/2)+cn,n>1 \end{cases}

当k>2时递归展开的深度logaN,a=k/(k-1)，超过了logn。

快速排序

分治法同时还可以勇于实现另一种不同的排序方法：快速排序，这也是c库函数里常用的sort()函数所使用的方法，在这种方法中，n个元素被分为了3段，左段left,右段right,和中段middle，中段仅包含一个元素，左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素，因此,left和right中的元素可以独立排序，并且不必对left和right的排序结果进行合并，Middle中的元素又被称为支点(pivot)。

伪代码：

void quicksort(){
    //从A[0:n-1]中选择一个元素作为middl，该元素就是支点
    T *left,*right//两个指针，指向left段大于支点和right指向小于支点的元素
    //交换两个元素，并更改指针
    //直至left中的元素都小于等于支点&&right中的元素都大于支点
    while(true){
        do{
           left=left+1;//寻找左段大于支点的元素
        }while(A[left]<pivot)
        do{
           right=right-1;//寻找右段小于支点的元素
        }while(A[right]>pivot)
        if(i>=j)break;//未发现交换对象就退出了
        swap(A[left],A[right]);//交换元素
    }
    quicksort(left);//递归调用对left段进行排序
    quicksort(right);//递归调用对right进行排序
    最终结果为left+middle+right
}

需要的递归栈空间为O(n)，如果使用堆栈将递归转化为迭代并每次划分后将长度较大的段压入栈中，则栈空间长度为O(logn)。在最坏的情况，left总是空的，则快速排序所需要的计算时间为O(n^2)，在最好的情况，left和right元素数目大致相同，快速排序的复杂性为O（nlongn)。平均复杂度也为O(nlogn)。

思考:为什么最坏情况时间复杂度为O(n^2)?

递归式为

T(n)=T(0)+T(n-1)+O(n)\\ =O(1)+T(N-1)+O(n)\\ =T(n-1)+O(n) =O(n^2)

Master定理可以知道就是O(n^2)。当然我们也可以使用迭代展开思考，如下图：

迭代深度为n，每次的值为单调递减数列，求和即得。

思考:为什么最好情况时间复杂度为O(nlogn)?

如果恰巧每次支点都在中间点，那么递归式为

T（n)=2T(n/2)+O(n)=O(nlogn)

但是我们发现如果支点落在(1/10n,9/10n)时，也有时间复杂度为O(nlogn)：

即快速排序中支点总是大概率容易落在好情况的位置上，所以平均情形也是好情况为o(nlogn)。

各种排序的算法复杂性比较

方法	最坏复杂性	平均复杂性
冒泡排序	n^2	n^2
计数排序	n^2	n^2
插入排序	n^2	n^2
选择排序	n^2	n^2
堆排序	nlogn	nlogn
归并排序	nlogn	nlogn
快速排序	n^2	nlogn

各排序算法平均时间的曲线图

选择问题

对于给定的n个元素的数组A[0:n-1]，要求从中找出第k小的元素。这种问题解决时间可以限制在O(nlogn)内，就是先对n个元素进行排序，然后取出A[k-1]就好了，若使用快速排序，可以获得更好的平均性能，尽管该算法在最坏情况下有一个比较差的渐进复杂性O(n^2)。伪代码就不写了，就是快排+取元素。

中间的中间规则优化快排最坏情况

如果仔细选择支点元素，则最坏情况是可以控制在O(n)的，其规则如下，首先将A中的n个元素分成n/r个组，r为某一整型常数，除了最后一组(毕竟有时候剩下的没有r个元素)，对每组中的r个元素进行排序来寻找每组中的中间元素，最后将这些中间元素排序，求得中间之中间支点元素。

例题：n考察如下情形：r=5, n=27, 并且a=[2，6，8，1，4，10，20，6，22，11，9，8，4，3，7，8，16，11，10，8，2，14，15，1，12，5，4 ]。这27个元素可以被分为6组，每组的中间元素分别为4 , 11 , 7 , 1 0 , 1 2和4，这些中间元素的中间元素为7，将其取为支点元素。

距离最近的点对

给定平面上的n个点，找其中的一对典，使得在n个点所组成的所有点对中，该点对间的距离最小。因为最接近点对可能不止一对，为了方便起见，我们只找其中的一对作为问题的解。一个最简单暴力的方法就是将每一个点都和其他的n-1个点相连，然后找出最小距离的点对即可。该方法的时间复杂性是T(n)=n(n-1)/2+n=O(n^2),效率低。

我们先考虑一维的情况，即平面S中的n个点退化为一条直线x轴上的n个实数x1,x2,…,xn，最接近点对就是这n个实数中相差最小的2个实数(所以也必定是相邻的两实数)，简单的方法就是排序这n各数，然后一次性扫描就可以找到最接近点对，时间复杂度为T(n)=O(nlogn)，如下图：

将S分为S1和S2，那么最接近点对就是在S1中最接近点对{p1,p2}和S2中最接近点对{q1,q2}或者某个{p3,q3}（p3在S1,q3在S2）。其中如果最接近点对好巧不巧是{p3,q3}，那么即|p3-q3|<d(d是min{(p1,q1),(p2,q2)})。则p3和q3两者与m的距离都不超过d,所以(m-d,m]中至多包含S中的一个点，同理(m,m+d]也是，所以p3,q3就找到了。

可是这种面中点映射到实数轴上的实数方法无法推广到二维情形。

小作业

Questions

给定自然数1, … , n的一个排列，例如，(1, 3, 4, 2, 5)，如果 j>i,但j 排在i 的前面则称(j, i)为该排列的一个逆序。在上例中 (3, 2)，(4, 2) 为该排列的逆序。该排列总共有2 个逆序。试用分治法设计一个计算给定排列的逆序总数的算法，要求算法的时间复杂度为Θ(nlog2n)。

Answers

有手就行吧，就不给了，上网就能找到答案。

总结

本次分治思想我们对排序有了更进一步的了解，其中快排，归并都是时间复杂度较为理想的排序，残缺棋盘，矩阵相乘，找最小值或最近距离可以尝试使用分治思想解决，那么本次分享就高于段落啦，希望你有所收获😘！