算法设计与分析 10算法设计-分治法.ppt

算法设计与分析
——分治法
2018/9/28
1
算法设计与分析演示稿纪玉波制作(C)
分治法(divide-and-conquer)
分治策略是一种用得最多的一种有效方法,它的基本思想将问题分解成若干子问题,然后求解子问题。子问题较原问题无疑是要容易些,由此得出原问题的解,就是所谓的“分而治之”的意思。分治策略还可以递归进行,即子问题仍然可以用分治策略来处理,最后的问题是非常基本而简单。下面举几个例子。
2018/9/28
2
算法设计与分析演示稿纪玉波制作(C)

合并算法排序即属于分治方法。合并(Merge)就是将两个或多个有序表合并成一个有序表,例如下图所示的两个有序表经合并运算后得到一个有序表。我们在此只用到两个有序表的合并,称为二路并〔Two-way merge)。
2018/9/28
3
算法设计与分析演示稿纪玉波制作(C)
合并排序(Merge sort)就是利用这种合并过程进行排序,即先将n个数据看成n个长度为l的表,将相邻的表成对合并,得到长度为2的n/2个有序表;进一步再将相邻表成对会并,得到长度为4的n/4个有序表;……;如此重复做下去,直至所有数据均合并到一个长度为n的有序表为止,即完成排序。上述每一次的合并过程称为一趟〔Pass),整个排序过程叫二路合并排序。下图是二路合并排序过程的一个例子。
2018/9/28
4
算法设计与分析演示稿纪玉波制作(C)
[7] [15] [13] [10] [4] [20] [19] [8]
[7] [15] [10] [13] [4] [20] [8] [19]
[7] [10] [13] [15] [4] [8] [19] [20]
[4] [7] [8] [10] [13] [15] [19] [20]
2018/9/28
5
算法设计与分析演示稿纪玉波制作(C)
对于二路合并,如果数据个数n是2的整数次方,则所需的趟数为logn,例如n=8,logn=3,故共需三趟合并过程。如果n不是2的整数次方,则在每趟合并时表的数目不一定总是偶数个。若表的数目为奇数,就剩下一个表要“轮空”,直接进入下一趟。这样,下一趟合并时此表的长度与其它的表将不相同,因此我们设计的合并过程,并不要求待合并的两个表长度必须相同。
二路合并排序的时间复杂性为O(nlogn),与堆排序及快速排序平均情况的时间复杂性同样数量级。
2018/9/28
6
算法设计与分析演示稿纪玉波制作(C)
{x1, x2,…, xn}中,找出最大和最小的数。
若用普通的算法为:
begin
xmax←x1;xmin←x1
for i=2 to n do
begin
if xmax<xi then xmax←xi
if xmin>xi then xmin←xi
end
end
2018/9/28
7
算法设计与分析演示稿纪玉波制作(C)
此算法的比较次数为2(n-1)=2n-2,显然不是最优的。如果用分治法解决法,写出递归过程为:
过程MAXMIN(x1, x2,…, xn)
(1)如n=1,则xmax←x1, xmin←x1
(2)如n=2,则比较x1与x2,令大者为xmax,小者为xmin
(3)如n>2,则
调用MAXMIN(x1, …, x[n/2])
调用MAXMIN(x[n/2]+1,…, xn)
比较两个最大值,令大者为xmax
比较两个最小值,令小者为xmin。
2018/9/28
8
算法设计与分析演示稿纪玉波制作(C)
下面分析用此算法的比较次数。设T(n)表示元素个数为n时的总比较次数,则
T(1)=0,T(2)=1
(n>2)
为方便起见,设n=2r,问题的逐层划分如下表所示:
可以证明
T(n)=3n/2-2
此值恰好等于问题的下界,故这是最优算法。
2018/9/28
9
算法设计与分析演示稿纪玉波制作(C)
其实,此问题也不一定要用递归算法来解决,可将数据分成两个一组的n/2组,第一组比较一数,令大的为xmax,小的为xmin,以后各组比较三次,先两个数据比较,其中大者再与xmax比,小者再与xmin比,总比较次数也恰为。
2018/9/28
10
算法设计与分析演示稿纪玉波制作(C)