首页计算机计算机基础计算机算法设计与分析 03 第4章 分治法.pptx

03 第4章 分治法.pptx

页数:69页文件大小:436.7 KB来源: 计算机算法设计与分析ppt课件

本课件系统讲解分治法,先给出分治策略的一般方法、DANDC抽象化控制与递归方程的时间分析,再依次展开二分检索、找最大和最小元素、归并分类、快速分类、选择问题与斯特拉森矩阵乘法六个典型算法,并对每个算法给出伪代码、执行实例与复杂度推导。

第四章分治法章节封面,标示本章主题为分治策略及其典型算法
第四章目录页,列出一般方法、二分检索、找最大最小元素、归并分类、快速分类、选择问题与斯特拉森矩阵乘法
分治法引入页,说明输入规模很大时把大问题分割成规模较小的相同问题以便各个击破
查看本课件的文字版(共 69 页,供检索与复制)

第1页:第四章 分治法章节封面

第四章分治法

第2页:第四章主要内容

24.1一般方法4.2二分检索4.3找最大和最小元素4.4归并分类4.5快速分类4.6选择问题4.7斯特拉森矩阵乘法主要内容

第3页:分治法的引入

3输入规模相当大时,直接求解很困难。

分析问题的特征,选择适当的设计策略。

将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

4.1一般方法

第4页:分治法的基本思想

4

  • 分治法的思想:将一个输入规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题性质相同,求出这些子问题解后,可以用适当的方法将各子问题的解合并成原问题的解。问题(n个输入)子问题1子问题2子问题k…子问题1子问题2子问题k…相同类型合并解

第5页:分治法的三个步骤

5步骤:分(divide)二分为主多分比二分更好吗?治(conquer)递归调用,当规模足够小时直接处理合(combine)4.1一般方法

第6页:分治策略DANDC抽象化控制

6 分治策略DANDC的抽象化控制 procedure DANDC(p,q) global n, A(1:n); integer m, p, q;//1≤p≤q≤n//ifSMALL(p,q) then return(G(p,q)) else m←DIVIDE(p,q) return(COMBINE (DANDC(p,m), DANDC(m+1,q))) endif end DANDC判断输入规模q−p+1是否足够小,可直接求解G是直接求解该规模问题的函数分割函数,p≤m≤q,原问题被分为A(p:m)和A(m+1:q)两个子问题合并函数,将两个子问题的解合并为原问题的解原问题为A(1:n) ,最初调用函数应该是DANDC(1, n);DANDC(p, q)是计算A(p: q)子问题的解.4.1一般方法

第7页:二分策略DANDC的计算时间

7

  • 二分策略DANDC的计算时间倘若所分成的两个子问题的输入规模大致相等,则分治策略DANDC的计算时间可表示为:说明:T(n):输入规模为n时,分治策略的计算时间g(n):对足够小的输入规模能直接计算出答案的时间f(n):COMBINE函数合成原问题解的计算时间g(n)n足够小2T(n/2)+f(n)否则T(n)=4.1一般方法

第8页:k分法的复杂性分析

8k分法的复杂性分析一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。

设分解阈值n0=1,且解规模为1的问题需耗费常数时间。

再设将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f(n)时间。

用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:通过迭代法求得方程的解:注意:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。

通常假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1).

第9页:二分检索问题描述

9

  • 问题描述:已知一个按非降序排列的元素表a1, a2, … ,an,判定某个给定元素x是否在该表中出现,若是,则找出该元素在表中的位置,并将下标值赋给j,否则置j为0.
  • 二分检索原理将二分检索问题表示为:I=(n, a1, … , an, x)选取一个下标k,可得到三个子问题
  • I1=(k−1, a1, … , ak-1, x)
  • I2=(1, ak, x)
  • I3=(n−k, ak+1, … , an, x)4.2二分检索对所求解的问题(或子问题)所选的下标都是中间元素的下标:k=⌊(n+1)/2⌋

第10页:二分检索算法

10 procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n;low←1; high←n while low≤high domid←⌊(low+high)/2⌋ case:x<A(mid): high←mid−1 :x>A(mid): low←mid+1 : else: j←mid; return; end case repeatj←0 end BINSRCH 二分检索算法

第11页:二分检索实例

  • 11检索x=9,9=A(5),一次比较就成功,最好情况101825423970−6−15A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)①②③③④②③④检索x=−15,−15<A(5),−15<A(2),−15= A(1),3次比较,成功检索x=101, 101>A(5), 101>A(7), 101>A(8),101= A(9),4次比较,成功检索x=8, 8<A(5), 8>A(2), 8>A(3), 8>A(4), 4次比较,不成功检索
  • 二分检索实例:设在A(1:9)中顺序放了以下9个元素:②

第12页:二分检索正确性证明

12

  • 用五个特性判断是否是一个算法
  • 证明算法正确性
  • 假定:比较运算能恰当地执行,过程中所有的语句按要求工作
  • 初始状态:low=1, high=n, n≥0, A(1)≤…≤A(n).
  • n=0
  • n>0二分检索算法正确性证明

第13页:二分检索的空间与时间

13

  • 二分检索算法所需的空间和时间
  • 所需空间:用n个位置存放数组A,还有low, high, mid, x, j五个变量需要存储,共需空间n+5
  • 所需计算时间:对于计算时间,需要分别考虑以下几种情况:成功检索的最好情况、平均情况、最坏情况不成功检索的最好情况、平均情况、最坏情况4.2二分检索

第14页:成功与不成功检索的情形

  • 14101825423970-6-15A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)4323143234433344333
  • 成功检索有n种情况,不成功检索有n+1种情况成功:不成功:不论检索是否成功,算法的执行过程都是x与一系列中间元素A(mid)的比较过程,可以用一棵二元比较树来描述算法的执行过程。

第15页:二元比较树

15

  • 二元比较树内结点表示一次元素的比较,存放一个mid值外结点表示不成功检索的一种情况592-61-1530754476238829101一条路径表示一个元素的比较序列4.2二分检索

第16页:定理4.2与比较次数

16

  • 二分检索的时间复杂度定理4.2:若n在区域[2k-1, 2k)中,则对于一次成功的检索,二分检索算法至多作k次比较,而对于一次不成功的检索,或者作k−1次比较或者作k次比较。4.2二分检索证明:考察二分检索算法执行过程的二元比较树:成功检索--内结点,不成功检索--外结点由于2k−1≤n <2k,内结点级数≤k,外结点级数≤k+1成功检索所需要的元素比较次数=级数,不成功检索所需要的元素比较次数=级数−1.

第17页:二分检索的时间复杂度

二分检索各种情况下的计算时间:以元素个数 n=9 的实例说明,成功检索与不成功检索的比较次数均不超过 4 次。

二分检索在各种情况下的计算时间
检索情况最好情况平均情况最坏情况
成功的检索Θ(1)Θ(logn)Θ(logn)
不成功的检索Θ(logn)Θ(logn)Θ(logn)

第18页:确切比较次数的讨论

18关于确切比较次数的讨论:•BINSRCH的 case语句:元素比较次数的假定不合理,但对时间的近似表示无影响。•实际上可以用if语句替代BINSRCH相应 case语句If x<A(mid) then high←mid−1 else if x>A(mid) then low←mid+1 else j←mid; return endif endif•每次循环固定一次比较的BINSRCH1算法Case:x<A(mid): high←mid−1:x>A(mid): low←mid+1: else: j←mid; return; end case

第19页:BINSRCH1算法

19 procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n;low←1; high←n+1/×high总比可能的取值大1×/ while low<high−1domid←⌊(low+high)/2⌋ if x<A(mid) thenhigh←mid elselow←mid/×x≥A(mid)×/ endif repeat if x=A(low) thenj←low /×检索成功×/ else j←0/×检索失败×/ endif end BINSRCH 二分检索算法

第20页:检索时间下界的思考

20

  • 以比较为基础检索的时间下界思考:对于已排序的n个元素,检索某元素x是否出现,是否存在以比较为基础的检索算法,在最坏情况下该算法比二分检索算法在计算时间上有更低的数量级?对于以比较为基础的检索算法的分析,采取构建二元比较树的方式。

第21页:顺序检索的二元比较树

21二元比较树-顺序检索n个元素存在如下关系的:A(1)<A(2)…<A(n),检索一给定元素x是否在A中出现x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功线性检索

第22页:二分检索的二元比较树

22二元比较树-二分检索X:A(⌊(n+1)/2⌋)X:A(⌊(3n+1)/4⌋)X:A(⌊(n+1)/4⌋)X:A(n)X:A(⌊(n+1)/2⌋+1)X:A(⌊(n+1)/2⌋-1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功…………

第23页:定理4.3检索时间下界

23

  • 以比较为基础检索的时间下界
  • 定理4.3:设A(1:n)含有n(n≥1)个不同的元素,排序为A(1)<A(2)<…<A(n);又设用以比较为基础去判断是否x∈A(1:n)的任何算法在最坏情况下所需的最小比较次数是FIND(n),那么FIND(n)≥⌈log(n+1)⌉.定理表明:任何一种以比较为基础的检索算法,其最坏情况下的计算时间都不可能低于O(logn),也就是不可能存在其最坏情况下计算时间比二分检索算法的计算时间数量级还低的算法。结论:二分检索是解决检索问题的最优的最坏情况算法。

第24页:找最大和最小元素问题

244.3找最大和最小元素 问题描述:在含有n个不同元素的集合中同时找出它的最大和最小元素 procedure STRAITMAXMIN(A,n,max,min)int i , n;max←min←A[1]; for i ←2 to n do{ if A[i]>max then max←A[i]; if A[i]<min then min←A[i];}endSTRAITMAXMIN直接算法:依次比较n-1个元素,同时记录下最大、最小的元素 if A[i]>max then max=A[i]; else if A[i]<min then min=A[i]; 直接算法的时间复杂度在最好、最坏、平均情况下均为2(n-1)改进后的计算时间:(元素升序)最好情况为(n-1)(元素降序)最坏情况为2(n-1)平均情况为3/2(n-1)改进

第25页:分治策略求最大最小元素

25采用分治策略求最大最小元素I=(n,A(1),…,A(n))划分为I1=(⌊n/2⌋,A(1),…,A(⌊n/2⌋) )I2=( n-⌊n/2⌋,A(⌊n/2⌋+1),…,A(n) )结果的合并

第26页:MAXMIN过程

26 分治法求最大和最小元素 procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n); casei= j: fmax ←fmin←A[i]i= j-1: if A[i]<A[j] then { fmax←A[j]; fmin←A[i]; } else { fmax←A[i]; fmin←A[j]; } else: {mid←(i+j)/2; call MAXMIN( i, mid, gmax, gmin) call MAXMIN(mid+1, j, hmax, hmin)fmax←max(gmax, hmax);fmin←min(gmin, hmin);} end case end MAXMIN只有一个或两个元素时递归调用部分两个子问题的答案进行合并4.3找最大和最小元素

第27页:MAXMIN执行实例

27(9)(8)(7)(6)(5)(4)(3)(2)(1)A4731176015-8-51322元素1,9,1,3,4,5,3,3,1,2,1,5,6,9,8,9,6,7,①22,13②-5,-5③22,-5④15,-8⑤22,-8⑨60,-8⑧60,17⑥60,17⑦47,31实例: A(1:n), n=9 ,元素具体如下表所示:4.3找最大和最小元素

第28页:MAXMIN的元素比较次数

28

  • 过程MAXMIN的时间复杂度MAXMIN的元素比较次数当n=2k(k是某个正整数)时,有T(n)=3n/2-2T(n)= 2T(n/2)+2= 2(2T(n/4)+2)+2= 4T(n/4)+4+2……= 2k-1T(2)+( 2k-1+2k-2+…+22+2 )=2k-1+2k-2=3n/2-2与直接算法的比较次数2(n-1)相比,比较次数减少了25%。0n=11n=2T(n)=T( n/2 )+ T( n/2 )+2n>24.3找最大和最小元素

第29页:MAXMIN的存储空间分析

  • 29可以证明:任何一种以比较为基础的找最大和最小元素的算法,其元素比较次数的下界为3n/2-2但是不代表该算法最优,理由如下
  • MAXMIN算法分析
  • MAXMIN所需的存储空间比直接算法多4.3找最大和最小元素给出n个元素,则MAXMIN算法有logn +1级的递归,每次递归都需要保存i, j, fmax, fmin和返回地址5个值直接算法需要空间为:n+3,用n个位置存放数组A,还有i, max, min三个变量需要存储

第30页:MAXMIN的频率计数

30

  • 元素A(i)和A(j)的比较与i和j的比较时间相差不大时,过程MAXMIN不可取。设MAXMIN的频率计数为C(n),n=2k, k为整数,当n>2时,有:C(n)=5n/2-34.3找最大和最小元素C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3= 4C(n/4)+6+3……= 2k-1C(2)+3*( 2k-2+2k-3+…+22+21+20)=2k+3*(2k-1-1)=2k+3*2k-1-3=5n/2-32n=2C(n)=2C( n/2 )+ 3 n>2

第31页:MAXMIN与直接算法的结论

31

  • 直接算法的比较次数为2(n-1),加上实现for循环需要的比较次数,则为3(n-1),虽然3(n-1)略大于5n/2-3,但MAXMIN算法还有递归所带来的时间开销,这种情况下直接算法要快一些
  • 结论:如果数组A的元素之间的比较远比整型变量的比较代价昂贵,则分治法产生效率较高的算法;反之则得到一个效率较低的程序。4.3找最大和最小元素

第32页:归并分类问题描述

32 直接方法(插入法) for j←2 to n do将A(j)放入已分类集合A(1:j−1) repeat4.4归并分类 问题描述:给定一个含有n个元素的集合,把它们按一定的次序分类(如非降次序)

第33页:插入分类算法

33 procedure INSERTIONSORT(A, n)A(0)←−∞ for j←2 to n doitem←A(j);i←j−1; while ( item<A(i)) doA(i+1)←A(i); i←i−1; repeatA(i+1)←item; repeat end INSERTIONSORT 插入分类算法描述数组元素的比较和移动将本次考虑的元素插入相应位置可能执行0~j次(j=2,3…n)最好情况Ω(n)最坏情况的计算时间:2+…+n=(n(n+1)/2)−1=Θ(n2)用item保存当前元素值4.4归并分类

第34页:分治策略设计归并分类

34分:平均分为2个子集合治:递归调用分类算法,将2个子集合分类合:将2个分类的子集合并为一个分类集合4.4归并分类分治策略设计归并分类算法

第35页:归并排序算法描述

35递归调用,分别对分解出来的两个子问题排序合并两个已排好的序列,得到原问题的解 归并排序算法描述Procedure MERGESORT(low,high)int low, high, mid; if (low<high) then mid←⌊(low+high)/2⌋ callMERGESORT(low,mid) callMERGESORT(mid+1,high) callMERGE(low,mid,high) end MERGESORT4.4归并分类

第36页:合并函数MERGE

36 合并函数MERGE的算法描述 procedure MERGE(low, mid, high)int h,i,j, k, low, mid, high; global A(low : high); local B(low : high);h←low; i←low; j←mid+1;while(h≤midandj≤high)do if (A(h)≤A(j)) then { B(i)←A(h); h←h+1; } else { B(i)←A(j); j←j+1; }i←i+1; repeat if (h>mid) then fork←jtohighdo{B(i)←A(k);i←i+1} else fork←htomiddo{B(i)←A(k);i←i+1 }fork←lowtohighdoA(k)←B(k); end MERGE处理两个已分类的序列剩余元素处理过程将已分类的集合复制到A数组4.4归并分类

第37页:MERGESORT执行过程

37

  • MERGESORT执行过程1,54,51,35,54,43,31,21,12,2表示一次调用时的low和high的值只含单个元素的子集合1, 1, 24, 4, 51, 2, 31, 3, 5表示MERGE调用时low, mid, high的值4.4归并分类

第38页:MERGE合并过程示例一

38A(5)A(4)A(3)A(2)A(1)351652179285310low=1; mid=1; high=2;h=1; i=1; j=2;while(h≤mid and j≤high)do{ if A(h)≤A(j) then … else { B(i)←A(j); j←j+1=3 ;i←i+1=2; }B(5)B(4)B(3)B(2)B(1)285310310285 if (h>mid) then … else for k=1 to 1 do { B(i)←A(h); i←i+1=3; } for k=1 to 2 do A(k)←B(k);4.4归并分类

第39页:MERGE合并过程示例二

39low=1; mid=2; high=3;h=1; i=1; j=3;while(h≤mid and j≤high)do{ if A(h)≤A(j) then … else{ B(i)←A(j); j←j+1=4 }i←i+1=2; } if (h>mid) then … else for k=h to mid do {B(2)←A(k);i←i+1=3 }{ B(3)←A(k); i←i+1=4 } for k=1 to 3 do A(k)←B(k);A(5)A(4)A(3)A(2)A(1)351652179310285B(5)B(4)B(3)B(2)B(1)1792853103102851794.4归并分类

第40页:MERGE合并过程示例三

40low=4; mid=4; high=5;h=4; i=4; j=5;while(h≤mid and j≤high)do{ if A(h)≤A(j) then … else { B(i)←A(j); j←j+1=6 }i←i+1=5; } for k=4 to 5 do A(k)←B(k); if (h>mid) then … else for k=4 to 4 do {B(5)←A(4); i←i+1=6; }A(5)A(4)A(3)A(2)A(1)351652310285179B(5)B(4)B(3)B(2)B(1)3516526523514.4归并分类

第41页:MERGE合并过程示例四

41low=1; mid=3; high=5;h=1; i=1; j=4;while(h≤mid and j≤high)do{ if A(h)≤A(j) then { B(i)←A(h); h←h+1=2 ; i←i+1=2; } if (h>mid) then for k=4 to 5 do { B(4)←A(4); i←i+1=5 } for k=1 to 5 do A(k)←B(k);{ B(5)←A(5); i←i+1=6 }{ if A(h)≤A(j) then { B(i)←A(h); h←h+1=4 ;i←i+1=4; }{ if A(h)≤A(j) then { B(i)←A(h); h←h+1=3 ;i←i+1=3; }A(5)A(4)A(3)A(2)A(1)652351310285179B(5)B(4)B(3)B(2)B(1)1792853103516526523513102851794.4归并分类

第42页:归并分类的计算时间

42

  • 归并分类的计算时间T(n)=an=1 , a是常数2T(n/2)+cnn>1 , c是常数当n=2k时,可得T(n)=2(2T(n/4)+cn/2)+cn= 22T(n/4)+2cn= 22(2T(n/8)+cn/4)+2cn= 23T(n/8)+3cn……= 2kT(1)+kcn= an+cnlogn如果2k<n<2k+1,有T(n)≤T(2k+1)则有T(n)=O(nlogn)归并2个子数组所需的元素比较次数在n/2到n-1之间4.4归并分类

第43页:归并分类算法的缺点与改进

43

  • 归并分类算法的缺点缺点1:当子集合的元素很少时,算法的很多时间消耗在递归的处理上。改进:当子集合的元素个数适当少时,采用在小规模集合上能有效工作的插入分类算法进行排序,而不是继续划分,以此克服上述缺点带来的时间消耗。缺点2:辅助数组B的使用增加了算法的空间,且每次调用MERGE时,都需要将B中的结果复制回A中,消耗了一部分时间。改进:用一个链接数组LINK(1:n)代替B,LINK中的元素为A中元素的下标,它指示下一个元素所在的下标位置。4.4归并分类

第44页:关于LINK数组

44

  • 关于LINK数组LINK(1:n)为一链接数组,取值范围为1, 2, …, n。可看成是A元素的指针,在分类表中它指向下一个元素所在的下标位置,用0表示结束。实例:下面是一个LINK集合,包含了两个已分类的子集合。q和r表示两个子集合的起始处:q=2,r=5(8)(7)(6)(5)(4)(3)(2)(1)60781043q=2的表为(2, 4, 1, 3) A(2)≤A(4)≤A(1)≤A(3)r=5的表为(5, 8 , 6, 7) A(5)≤A(8)≤A(6)≤A(7)(8)(7)(6)(5)(4)(3)(2)(1)4689582335693243数组A:数组LINK:4.4归并分类

第45页:改进的MERGESORT1算法

45 procedure MERGESORT1(low, high,p) global A(low:high), LINK(low:high) if (high−low+1<16 ) then call INSERTIONSORT(A,LINK, low, high,p); else mid←⌊(low+high)/2⌋; call MERGESORT1(low, mid,q); call MERGESORT1(mid+1, high,r); call MERGE1(q,r,p); endif end MEGESORT1 改进的归并分类算法当集合元素小于16时,调用修改的插入分类算法归并分类递归调用合并两个子问题的解4.4归并分类

第46页:使用LINK数组的MERGE1

46 使用LINK数组的归并函数 procedure MERGE1(q, r, p) global n, A(1:n), LINK(0:n);int i, j, k;i←q; j←r; k←0; while (i≠0 and j≠0) do if (A(i)≤A(j)) then LINK(k)←i;k←i;i←LINK(i); else LINK(k)←j;k←j;j←LINK(j); if (i=0) then LINK(k)←j; else LINK(k)←i;p←LINK(0); end MERGE1当q和r非空时进行以下操作:加入一个关键字的下标到LINK数组中处理剩下的关键字4.4归并分类

第47页:MSORT1执行实例

47(8)(7)(6)(5)(4)(3)(2)(1)]5535701530251050数组A:MSORT1(1, 8, p) if (8-1+1<5 ) thenISTSORT(A,LINK,1,8,p); elsemid=(1+8)/2=4 ;MSORT1(1, 4,q);MSORT1(5, 8,r);MERGE1(q, r, p); end MSORT1MSORT1(1, 4,q) if (4-1+1<5 ) thenISTSORT(A,LINK,1,4,p); end MSORT1返回q=2MSORT1(5, 8,r) if (8-5+1<5 ) thenISTSORT(A,LINK,5,8,p); end MSORT1返回r=5MERGE1(2,5,p);(8)(7)(6)(5)(4)(3)(2)(1)(0)000000000数组LINK:143068074.4归并分类25

第48页:MERGE1执行实例

48(8)(7)(6)(5)(4)(3)(2)(1)(0)680714300数组LINK:MERGE1(2, 5, p)i=2; j=5; k=0; while (i≠0 and j≠0) do if (A(2)≤A(5)) then LINK(0)=2; k=2; i=LINK(2)=3;2534718(8)(7)(6)(5)(4)(3)(2)(1)5535701530251050 if (A(3)≤A(5)) else LINK(2)=5; k=5; j=7; if (A(3)≤A(7)) then LINK(5)=3; k=3; i=4; if (A(4)≤A(7)) then LINK(3)=4; k=4; i=1; if (A(1)≤A(7)) else LINK(4)=7; k=7; j=8; if (A(1)≤A(8)) then LINK(7)=1; k=1;i=0; if (i==0) then LINK(1)=8;p=LINK(0)=2;4.4归并分类

第49页:归并分类讨论

494.4归并分类讨论:1.可以消去递归,取消栈的使用,例如:①采用由底向上的方法,将元素两两配对;

②自然合并排序法;

2.空间代价3.适合于并行计算,采用并行或专用集成电路实现数据排序操作时,派生出许多算法,例如奇偶合并排序,双调合并排序等。

(8)(7)(6)(5)(4)(3)(2)(1)5535701530251050

第50页:由底向上的归并排序

  • 50(8)(7)(6)(5)(4)(3)(2)(1)5535701530251050(1)50(4)(3)(2)302510(6)(5)7015(8)(7)5535(4)(3)(2)(1)50302510(8)(7)(6)(5)70553515(8)(7)(6)(5)(4)(3)(2)(1)7055503530251510
  • 首先对数组A进行一遍扫描,找出所有已排序的子数组段
  • 然后将相邻的子数组段两两合并,重复这种合并过程,直到整个数组排好序4.4归并分类

第51页:分类算法的时间下界

  • 51任何以关键字比较为基础的分类算法,最坏情况下的时间下界都是Ω(nlogn),因此从数量级的角度上看,归并分类是最坏情况下的最优算法。采用二元比较树证明
  • 以比较为基础分类的时间下界4.4归并分类

第52页:三个关键字的二元比较树

52对3个关键字分类的二元比较树1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)<A(2)A(1)>A(2)A(2)<A(3)A(2)>A(3)A(1)<A(3)A(1)>A(3)A(2)<A(3)A(2)>A(3)A(1)<A(3)A(1)>A(3)表示一次比较一种可能的分类序列

第53页:最坏情况比较次数的下界

  • 532T(n)≥叶结点实际数≥n!满二叉树n关键词全排列n>1时,n!≥(n/2)n/2n≥4有,T(n)≥(n/2)log (n/2)≥(n/4)log nT(n) =Ω(nlog n)
  • 最坏情况下比较次数=比较树的最长路径=根到最远叶结点距离=树高T(n)4.4归并分类

第54页:快速分类的基本思想

544.5快速分类

  • 快速分类的基本思想:选取数组A中的某个元素t=A[s],然后将其他元素重新排列,使A中所有在t以前出现的元素都小于或等于t,而在t之后出现的元素都大于或等于t。这个重新整理的过程称为划分,t称为划分元素。A[n]…A[s+1]A[s]A[s-1]…A[2]A[1]划分元素t经过一次划分后A[n]…A[k]tA[j]…A[2]A[1]每个元素都小于或等于t每个元素都大于或等于t

第55页:快速分类实例

554.5快速分类

  • 快速分类实例A[7]A[6]A[5]A[4]A[3]A[2]A[1]8172935①第1次划分,选t=A[1],即t=5,划分后得到如下结果:A[7]A[6]A[5]A[4]A[3]A[2]A[1]8975132②第2次划分,选t=A[1],即t=2,划分后结果:A[7]A[6]A[5]A[4]A[3]A[2]A[1]8975321③第3次划分,选t=A[5],即t=7,划分后没有变化④第4次划分,选t=A[6],即t=9,划分后结果:A[7]A[6]A[5]A[4]A[3]A[2]A[1]8975321A[7]A[6]A[5]A[4]A[3]A[2]A[1]9875321

第56页:快速分类算法

564.5快速分类 procedure QUICKSORT(low,high)int low,high; global n, A(1:n)iflow<high then{ j←high+1 call PARTITION(low, j) call QUICKSORT(low, j-1) call QUICKSORT(j+1, high)} endif end QUICKSORT 快速分类算法划分A(low,high),函数执行完后, j返回划分元素的下标递归调用划分之后得到的两个集合

第57页:PARTITION划分过程

574.5快速分类 PARTITION划分过程的实现 procedure PARTITION(m, p)int m,p,i; global A(m:p-1)v←A[m];i←m; loop loop i←i+1 until A[i]≥v ; loop p←p-1 until A[p]≤v ; if (i<p) then call INTERCHANGE(A[i], A[p]) else exit repeatA[m]←A[p];A[p]←v; end PARTITION交换A[i]和A[p]结束过程时,参数p中的值为划分元素所在位置的下标,该值将带回,用于后面的QUICKSORT过程i从左向右移,直到A[i] ≥tp从右向左移,直到A[p]≤t

第58页:快速分类实例分析

58首先调用QUICKSORT(1,7)if 1<7 then{j=8; call PARTITION(1, 8); call QUICKSORT(low,j-1) call QUICKSORT(j+1, high)} end QUICKSORT4.5快速分类 快速分类实例分析过程等PARTITION(1, 8)调用结束后,返回参数j的值,才能执行递归调用PARTITION(m, p)loop(第1次) loop i++ until A[i]≥t; i=3 loop p-- until A[p]≤t; p=6 if (i<p) thenA[i]←↔A[p];A[7]A[6]A[5]A[4]A[3]A[2]A[1]8172935A[7]A[6]A[5]A[4]A[3]A[2]A[1]8972135

第59页:PARTITION执行细节

594.5快速分类A[m]=A[p];

即A[1]=A[4]=2A[p]=t;

即A[4]=5end

第60页:快速分类的时间复杂性

60•快速分类算法的分析I:时间复杂性假设前提互不相同;

随机选取划分元素划分单元随机选取的改进快速分类的性能取决于划分的对称性!随机选取更合理,因为最好能找到中间元素最坏情况下:划分算法比较次数为元素数:p-m+1第i级的比较次数:n-i+1 (实际上是固定的)最坏情况下级数为n-1(每次取最小或最大值)总和:n+(n-1)+…= O(n2)平均情况下:划分元素最终位置机会均等,运用概率公式得:

第61页:快速分类的栈空间与比较

61•快速分类算法的分析II:栈空间使用递归算法:最坏情况下O(n)改进的迭代算法:每次选择小的文件继续处理(较小的文件在处理过程中相对迭代次数少,可能产生的栈空间占用少)O(log n)归并分类和快速分类算法的比较

第62页:4.6 选择问题

62•选择问题定义•算法2.15•举例•分析:最坏情况下:O(n2)平均情况下:O(n)4.6选择问题

第63页:选择问题的算法要点

63

第64页:最坏情况线性时间的选择算法

64•构造最坏情况下O(n)的选择算法•二次中间值规则•粗略算法2.16•分析•Select2的实现

第65页:矩阵乘法的传统方法

  • 654.7Strassen矩阵乘法A和B的乘积矩阵C中的元素C(i,j)定义为:若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C(i,j),需要做n次乘法和n-1次加法。因此,计算出矩阵C中的n2个元素所需的计算时间为O(n3)
  • 传统方法:O(n3)

第66页:Strassen矩阵乘法的分块

66将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。

由此可将方程C=AB重写为:1969年,Strassen采用分治法:由此可得:复杂度分析4.7Strassen矩阵乘法

第67页:Strassen的复杂度分析

  • 67为了降低时间复杂度,必须减少乘法的次数。复杂度分析T(n)=O(nlog7) =O(n2.81)
  • 较大的改进4.7Strassen矩阵乘法

第68页:矩阵乘法方法的改进

68

  • 传统方法:O(n3)
  • 分治法:O(n2.81)
  • 更快的方法??
  • Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。
  • 因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。
  • 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)(1990年)
  • 是否可以一直改进下去?它的下界?未解决,平凡下界O(n2)
  • n较小时(n<45),且矩阵中非0元较少时,不宜采用此方法,当n相当大时,它才优于常规算法。4.7Strassen矩阵乘法D. CopperSmith,S. Winograd. Matrix multiplication via arithmetic progressions..Journal of Symbolic Computation .Vol. 9 (1990), pp. 251-280.

第69页:本章小结与作业

69小结

  • 一般方法
  • 二分检索
  • 归并分类
  • 斯特拉森矩阵乘法侧重算法设计和算法分析作业:2, 3, 5, 7, 11, 12, 23
顶部目录