分治法

分治法思想

  • 分治法设计算法的思想是:

    将问题分成(divide)多个子问题;

    递归地解决(conquer)每个子问题;

    将子问题的解合并(combine)成原问题的解。

  • 分治法常常得到递归算法;

  • Merge-Sort是用分治法设计算法的范例

  • 算法复杂性分析

    Master method

    Substitution method

适用条件

  • 分治法所能解决的问题一般具有以下几个特征:

    该问题的规模缩小到一定程度就可以容易地解决;

    该问题可以分解为若干个规模较小的子问题;

    利用该问题分解出的子问题的解可以合并为该问题的解;

    该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

  • 最后一条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。

基本步骤

1
2
3
4
5
6
7
8
9
10
divide-and-conquer(P)
{
if(P<=n0) adhoc(P); //解决小规模的问题
divide P into smaller subinstances P1,P2,...,Pk; //分解问题
for(int i=1;i<=k;i++)
{
yi=divide-and-conquer(Pi); //递归地解决各子问题
return merge(y1,...,yk); //将各子问题地解合并成为原问题的解
}
}

人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个字问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法好是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。

应用

1.Defective Chessboard

实例

  • n=pow(4,k);
  • 需要(n-1)/3个3-方块填满棋盘;
  • 算法的时间复杂度:t(n)=4t(n/4)+c,a=4,b=4,loga=1。∴t(n)=Θ(n)。

2.归并排序(Merge Sort)

  • 我们采用平衡分割法来分割n个元素,即将n个元素分为A和B两个集合,其中A集合中含有n/k个元素,B中包含其余的元素;
  • 然后递归地使用分治法对A和B进行排序;
  • 当A或B内元素<k时使用插入排序;
  • 然后采用一个成为归并(merge)的过程,将已排好序的A和B合并成一个集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void sort(T E,int n)
{//对E中的n个元素进行排序,k为全局变量
if(n>=k)
{
i=n/k;
j=n-i;
令A包含E中的前i个元素
令B包含E中余下的j个元素
sort(A,i);
sort(B,j);
merge(A,B,E,i,j); //把A和B合并到E
}
else 使用插入排序算法对E进行排序
}

算法复杂度:

设t(n)为分治排序算法,则有以下递推公式

当n/k≈n-(n/k)时,t(n)的值最小(balance原理)

因此,当k=2时,分治法通常具有最佳性能:当k>2时递归展开的深度超过 以2为底n的对数。

k=2时,有

3.快速排序(Quick Sort)

  • 分治法还可以用于实现另一种完全不同的排序方法:快速排序;
  • 在这种方法中,n个元素被分成三段,左短left,中段middle,右段right;
  • 中段仅包含一个元素;左段中各元素都小于等于中段元素;右段中各元素都大于等于中段元素。因此left和right中的元素可以独立排序,并且不必对left和right的排序结果进行合并,middle中的元素被成为支点(pivot)。
1
2
3
4
5
6
7
//伪代码
//使用快速排序方法对a[0:n-1]排序
//从a[0:n-1]中选择一个元素作为middle,该元素为支点
//把余下的元素分割成为两段,left和right,使得left中的元素都小于等于支点,right中的元素都大于等于支点
//递归地使用快速排序方法对left进行排序
//递归地使用快速排序方法对right进行排序
//所得结果为left+middle+right

快速排序的平均复杂性是Θ(nlogn)。

各种排序算法的比较

排序方法 比较次数 移动次数 稳定性 附加存储
最好 最差 最好 最差 最好 最差
直接插入排序 n 0 1 1
折半插入排序 nlogn nlogn 0 1 1
冒泡排序 n 0 1 1
快速排序 nlogn nlogn × logn
简单选择排序 0 n × 1 1
锦标赛排序 nlogn nlogn nlogn nlogn n n
堆排序 nlogn nlogn nlogn nlogn × 1 1
归并排序 nlogn nlogn nlogn nlogn n n

4.选择(Selection Problem)

  • 定义:对于给定的n个元素的数组a[0:n-1],要求从中找出第k小的元素;
  • 选择问题可在O(nlogn)时间内解决,方法是首先对这n个元素进行排序(如使用堆排序或归并排序),然后取出a[k-1]中的元素;
  • 若使用快速排序,可以获得更好的平均性。尽管该算法在最坏情形下有一个比较差的渐进复杂性O(n²)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<class T>
T Select(T a[],int n,int k)
{
//返回a[0:n-1]中第k小的元素
//假定a[n]是一个伪最大元素
if(k<1||k>n) throw OutOfBound();
return select(a,0,n-1,k);
}
template<class T>
T select(T a[],int l,int r,int k)
{
//在a[l:r]中选择第k小的元素
if(l>=r) return a[l];
int i=l;//从左至右的游标
int j=r+1;//从右到左的游标
T pivot=a[l];
//把左侧>=pivot的元素与右侧<=pivot的元素进行交换
while(1)
{
do{//在左侧寻找>=pivot的元素
i=i+1;
}while(a[i]<pivot);
do{//在右侧寻找<=pivot的元素
j=j-1;
}while(a[j]>pivot)
if(i>=j) break;//未发现交换对象
Swap(a[i],a[j]);
}
if(j-l+1==k) return pivot;
//设置pivot
a[l]=a[j];
a[j]=pivot;
//对一个段进行调用
if(j-l+1<k) return select(a,j+1,r,k-j+l-1);
else return select(a,l,j-1,k);
}

上述程序复杂度分析:

  • 最坏情况下复杂性是Θ(n²);

  • 如果left和right总是同样大小或者相差不超过一个元素,那么可以得到以下递归式:

  • 如果n是2的幂,则通过使用迭代方法,可以得到t(n)=Θ(n);

  • 提示:选择较好的pivot可得到较好的性能。

中间的中间规则:

  • 若仔细地选择支点元素,则最坏情况下的时间开销也可以变成Θ(n);
  • 一种选择支点元素的方法是使用“中间的中间(median-of-median)”规则:首相将数组a中的n个元素分成n/r组,r为某一整常数,除了最后一组外,每组都有r个元素。然后通过在每组中对r个元素进行排序来寻找每组中位于中间位置的元素。最后对所得到的n/r个中间元素,递归使用选择算法,求得“中间之中间”作为支点元素。

Example:

中间的中间实例

距离最近的点对

  • 问题描述:给定平面上n个点,找其中的一对点,使得在n个点所组成的所有点对中,该点对距离最小;
  • 严格来讲,最接近点对可能多于一对,为简便起见,我们只找其中的一对作为问题的解;
  • 一个简单的做法是将每一个点于其他n-1个点的句里算出,找出最小距离的点对即可。该方法的时间复杂性是T(n)=n(n-1)/2 + n = O(n²),效率较低;
一维空间中的情形
  • 为了使问题易于理解和分析,先来考虑一维的情形。此时,S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近的点对即为这n个实数中相差最小的两个实数;

  • 一个简单的办法就是先把x1,x2,…,xn排好序,再进行一次线性扫描就可以找出最接近点对,T(n)=O(nlogn)。然而这种方法无法推广到二维情形;

  • 假设我们用x轴上某个点m将S划分为2个子集S1和S2,基于平衡子问题的思想,用S中各点坐标的中位数来作分割点;

  • 递归地在S1和S2上找出最接近点对{p1,p2}和{q1,q2},并设d=min{|p1-p2|,|q1-q2|},S中的最接近点对或者是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中p3∈S1且q3∈S2;

  • 可以用线性时间就可以找到问题的解;

  • 分割点m的选取不当,会造成|Si|=1,|Sj|=n-1的情形,使得T(n)=T(n-1)+O(n)=O(n²)。这种情形可以通过“平衡子问题”方法加以解决:选取各坐标的中位数作分割点。

二维空间中的情形
  • 选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2;

  • 递归地在S1和S2上找出其最小距离d1和d2,并设d=min{d1,d2},S中的最接近点1对或者是d,或者是某个{p,q},其中p∈S1且q∈S2;

  • 复杂度分析

算法分析

  • 任何求最大最小的算法从起始状态到完成状态所用比较次数不可少于 (3n/2)(上取整)-2
  • (3n/2)(上取整)-2是所有基于比较的求最大最小算法所需比较次数的下界;
  • 堆排序,归并排序在最坏情况下有较好的性能(针对渐进复杂性而言);
  • 堆排序,归并排序,快速排序在平均情况下性能较优。