算法设计技巧与分析 分治法(第6章)

2024/3/210第六章分治法分治法的基本模式6.1

引言6.2

二分搜索6.3

归并排序6.4

分治法的基本模式应用6.5

选择:找第k小元素6.6

快速排序6.7

大整数的乘法6.8

矩阵乘法6.9

最近点对问题2024/3/2116.1引言问题在序列A[1..n]中找最小和最大元素。思想在序列A[1……n]中找最小和最大元素x,y[if(n<=2)直接比较得结果;else

在序列A[1……mid]中找最小和最大元素x1,y1;

在序列A[mid+1…..n]中找最小和最大元素x2,y2;x=min{x1,x2};y=max{y1,y2};]2024/3/2126.1引言Algorithm6.1MINMAX2024/3/2136.1引言2024/3/2146.1引言2024/3/2156.2二分检索问题在序列A[1..n]中查找x，若找到返回下标，否则返回0。思想在序列A[1……n]中找x[if序列长度n为0，返回0;elsecasex=A[mid]:返回mid;casex<A[mid]:在序列A[1……mid-1]中找x;casex>A[mid]:在序列A[mid+1…..n]中找x;]Algorithm6.2BINARYSEARCHERC最坏情况时间复杂度：

(logn)2024/3/2166.2二分检索算法分析

设C(n)表示算法对大小为n的数组在最坏情况下所指向的比较次数。则有如下递推式2024/3/2176.2二分检索

由于2024/3/2186.3归并排序问题将序列A[1..n]中元素按照升序排序。思想将序列A[1……n]中元素排序[if序列长度n>1

将序列A[1……mid]中元素排序;

将序列A[mid+1…..n]中元素排序;

归并两个有序序列A[1……mid]和A[mid+1…..n]；

]2024/3/2196.3归并排序2024/3/21106.3归并排序2024/3/21116.3归并排序算法分析 首先，假定n是2的幂，即n=2k。令C(n)表示n个元素排序需要比较的次数，显然n=1，有C(1)=0。当n>1，执行步骤3和4的比较次数都是C(n/2)。而步骤5的比较次数根据观察结论1.1可知介于n/2和n-1之间。因此所需的最小比较次数由下式确定：2024/3/21126.3归并排序

所需的最大比较次数则是：2024/3/21136.3归并排序2024/3/21146.4分治法的基本模式关键步骤划分：将输入分成p≤n个部分处理子问题：如果问题的规模大于某个预定的阈值n0，则执行p个递归调用。合并：组合p个递归调用的解来得到期望的输出值。合并步骤对于执行一个实际的分治算法是非常关键的，算法的效率很大程度上取决于如何明智地实现这一步。划分的步骤在几乎所有的分治算法中是不变的：把输入数据分成p部分，并且转到处理子问题这一步。因此，它的时间为O(n)，甚至是O(1)。2024/3/2115分而治之法算法的模式若问题实例I大小“较小”，则直接求解并返回结果；否则进行下一步；（divide）将I分成m个大小基本相同的子实例I1,I2,…,Im；（conquer）对于每个子实例递归地求解得到它们的解；（combine）将子实例的解合并得到实例I的解6.4分治法的基本模式2024/3/2116实例I

:

？

分解实例I

1:

？实例I2:

？……实例I

m:

？

分解……

递归求解实例I

1:

y1实例I

2:

y2……实例I

m:

ym

合并实例I

:

y分治法的直观描述2024/3/21176.5选择:找中值和第k小元素选择问题

找出序列A[1..n]中的第k小元素。特别地，当k=

n/2

时，即找中值元素。算法1：排序时间复杂度:

(nlogn)

寻找中项最直接的方法是对所有元素排序并取出中间的一个元素。这个算法需要(nlogn)时间。2024/3/21186.5选择:找中值和第k小元素算法2：一个最坏时间复杂度为

(n2)的分治法思想

对于集合A[1..n]中的元素，用其中某元素v进行划分：

A1={a|a<v且aA}，

A2={a|a=v且aA}，

A3={a|a>v且aA}。

case|A1|

k：问题归结为在A1中找第k小元素；

case|A1|+|A2|>=k：v就是第k小元素；

case|A1|+|A2|<k：问题归结为在A3中找第k-|A1|-|A2|小元素。 对于第一、第三种情形，在A1或A3上重复上述过程直到找到所要找的元素为止。

2024/3/2119算法3：一个最坏时间复杂度为

(n)的分治法思想

在上述算法中，划分元素为二次取中值得到，这样就保证了子问题A1或A3的大小变为A大小的p倍（p为常数且0<p<1）。由此所得算法的最坏情况时间为

(n)。Algorithm6.4

SELECT6.5选择:找中值和第k小元素2024/3/21206.5选择:找中值和第k小元素2024/3/2121例：假设A={8，33，17，51，57，49，35，11，25，37，14，3，2，13，52，12，6，29，32，54，5，16，22，23，7，65},寻找中项k=[26/2]=13。阈值由44对于本题过大，假设改为6，首先将数集划分为5组，

{8，33，17，51，57} {49，35，11，25，37} {14，3，2，13，52} {12，6，29，32，54} {5，16，22，23，7}{65}6.5选择:找中值和第k小元素2024/3/2122对每组进行排序

{8，17，33，51，57} {11，25，35，37，49} {2，3，13，14，52} {6，12，

29，32，54} {5，7，16，22，23}{65} M={33，35，13，29，16}

递归找到M中的中项：mm=296.5选择:找中值和第k小元素2024/3/2123将A分为三个子序列：A1={8，17，11，25，14，3，2，13，12，6，5，16，22，23，7}A2={29}A3={22，51，57，49，35，37，52，32，54，65}因为|A1|=15>k=13所以第13小的元素在A1中。令A=A1重复上述过程。6.5选择:找中值和第k小元素2024/3/2124A={8，17，11，25，14，3，2，13，12，6，5，16，22，23，7}将数集分为3组

{8，17，11，25，14} {3，2，13，12，6} {5，16，22，23，7}M={14，6，16} mm=14 A1={8，11，3，2，13，12，6，5，7} A2={14} A3={17，25，16，22，23}6.5选择:找中值和第k小元素2024/3/2125|A1|+|A2|=10<k=13，故第13小的元素在A3中。设A=A3，由于|A3|=5<设定的阈值6，故直接对A进行排序找到第3小的元素（3=13-10）。最终算法返回A[3]=22，也即给定的序列的中项是22。6.5选择:找中值和第k小元素2024/3/2126算法分析 如下图所示，已将数集中的元素划分为具有5元素的各个组，每个组从低到顶按升序排列。6.5选择:找中值和第k小元素2024/3/2127

令A1’表示小于或等于mm的元素集，A3’表示大于或等于mm的元素集，根据算法的定义，A1是严格小于mm的元素集，A3是严格大于mm的元素集，故：6.5选择:找中值和第k小元素2024/3/2128下面来分析算法的运行时间T(n)(1)(n)(n)(n)(1)T(0.7n+1.2)2024/3/2129

对于步骤7，希望去掉常量1.2，令0.7n+1.2≤，则有0.7n+1.2≤0.75-1，即当n≥44时，这个不等式成立。

故有下述递推式：6.5选择:找中值和第k小元素2024/3/21306.5选择:找中值和第k小元素2024/3/21316.6快速排序思想

快速分类算法是由著名的计算机科学家霍尔（C.A.R.Hoare）根据分治策略设计的一种高效率的分类算法。基本思想是，对于输入的子序列A[p..q]，快速分类分三步走：

(1)分解(Divide)：将A[p..q]划分成两个非空的子序列A[p..j]和A[j+1..q]，使得A[p..j]中的任一元素小于或等于A[j+1..q]中的任一元素。下标j在划分过程中确定.

(2)递归求解(Conquer)：通过递归调用快速分类算法分别对A[p..j-1]和A[j+1..q]进行分类。

(3)合并(Merger)：由划分的特点知，在A[p..j-1]和A[j+1..q]都分好类后不需任何计算A[p..q]就已分好类。2024/3/21326.6快速排序

QUICKSORT排序算法具有(nlogn)的平均运行时间，这个算法优于MERGESORT的一点是它在原位上排序，即对于被排序的元素，不需要辅助的存储空间。

下面介绍划分SPLIT算法，它是算法QUICKSORT算法的基础。2024/3/21336.6快速排序2024/3/21346.6快速排序例：将算法应用于数组{5，7，1，6，4，8，3，2}.2024/3/21356.6快速排序2024/3/21366.6快速排序快速排序算法思想

要排序的元素A[low…high]通过算法SPLIT重新排列元素，使得原先在A[low]中的主元占据其正确的位置A[w]，并且所有小于或等于A[w]的元素的位置处于A[low…w-1]，而所有大于A[w]的元素所处的位置是A[w+1…high]。子数组A[low…w-1]和A[w+1…high]递归地排序，产生整个排序数组。2024/3/21376.6快速排序2024/3/21386.6快速排序例：假设对数组{4，6，3，1， 8，7，2，5}排序。2024/3/21396.6快速排序快速排序算法时间复杂度分析最坏情况:

(n2)最好情况:

(nlogn)平均情况:

(nlogn)2024/3/21406.6快速排序最坏情况:

(n2)

最坏情况发生在输入数组已经是非降序排列的，而对于算法QUICKSORT的每次调用，都发生在主元A[low]是数组中最小的元素的情况，这意味着将得到w=low，因而仅存在一个有效的递归调用，而另一个调用成为对一个空数组的调用。

因此，如果算法从调用QUICKSORT(A,1,n)开始，下一步的两个递归调用分别是QUICKSORT(A,1,0)和QUICKSORT(A,2,n)，第一个是无效的调用。2024/3/21416.6快速排序

此时，对于quicksort的n次调用就为：

quicksort(A,1,n),quicksort(A,2,n),…,quicksort(A,n,n)

接着，调用SPLIT算法： SPLIT(A[1…n],w),SPLIT(A[2…n],w),…,SPLIT(A[n…n],w)

由于对于输入为j的元素，SPLIT算法执行的比较次数为j-1。故总的比较次数为

2024/3/21426.6快速排序2024/3/21436.6快速排序平均情况:

(nlogn)

有 可得2024/3/21446.6快速排序

将上式的n用n-1代替，可得 两式相减，整理后 令 可得 解得2024/3/21456.6快速排序2024/3/2146回顾一个递归方程的解

2024/3/2147回顾一个递归方程的解

2024/3/21486.7大整数乘法问题

设u和v分别两个n-bit的整数（n是2的k次幂），求其乘积uv。算法1

——传统算法：

(n2)算法2

——分治算法思想2024/3/21496.7大整数乘法2024/3/21506.7大整数乘法2024/3/21516.7大整数乘法2024/3/21526.7大整数乘法2024/3/21536.8矩阵乘法问题设A和B是nn矩阵，求其乘积C=AB.算法1——传统算法思想时间复杂度：

(n3)——n3次乘法和n3–n2次加法2024/3/21546.8矩阵乘法算法2——递归算法思想2024/3/21556.8矩阵乘法2024/3/21566.8矩阵乘法算法3——Strassen’salgorithm思想 算法的基本思想就是增加加减法的次数减少乘法的次数。这个算法最终用了7次n/2×n/2矩阵乘法和18次n/2×n/2矩阵加法。2024/3/21576.8矩阵乘法2024/3/21586.8矩阵乘法2024/3/21596.8矩阵乘法三个算法的比较2024/3/21606.9最近点对问题

最近点对问题

在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其它几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空中移动的一个点来看待，则具有最大碰撞危险的2架飞机就是空中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。给定平面上n个点(xi,yi)，1≤i≤n，找出其中的一对点，使得在n个点的所有点对中，该点对的距离最短。2024/3/2161

算法思想算法一（直接法）：通过检查所有的n(n-1)/2对点，并计算每一对点的距离，即可找出距离最近的一对点。这种方法所需的时间为O(n2)。算法二（分治法）：

1）当n较小时，用直接法求最近点对；

2）当n较大时，将点集分成大致相等的两部分A和B，（递归地）确定A和B中的最近点对，确定一点在A中，另一点