页数:69页文件大小:436.7 KB来源: 计算机算法设计与分析ppt课件
本课件系统讲解分治法,先给出分治策略的一般方法、DANDC抽象化控制与递归方程的时间分析,再依次展开二分检索、找最大和最小元素、归并分类、快速分类、选择问题与斯特拉森矩阵乘法六个典型算法,并对每个算法给出伪代码、执行实例与复杂度推导。
第四章分治法
24.1一般方法4.2二分检索4.3找最大和最小元素4.4归并分类4.5快速分类4.6选择问题4.7斯特拉森矩阵乘法主要内容
3输入规模相当大时,直接求解很困难。
分析问题的特征,选择适当的设计策略。
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
4.1一般方法
4
5步骤:分(divide)二分为主多分比二分更好吗?治(conquer)递归调用,当规模足够小时直接处理合(combine)4.1一般方法
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
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
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 二分检索算法
12
13
15
16
二分检索各种情况下的计算时间:以元素个数 n=9 的实例说明,成功检索与不成功检索的比较次数均不超过 4 次。
| 检索情况 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 成功的检索 | Θ(1) | Θ(logn) | Θ(logn) |
| 不成功的检索 | Θ(logn) | Θ(logn) | Θ(logn) |
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 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
21二元比较树-顺序检索n个元素存在如下关系的:A(1)<A(2)…<A(n),检索一给定元素x是否在A中出现x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功线性检索
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
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采用分治策略求最大最小元素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 分治法求最大和最小元素 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(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
30
31
32 直接方法(插入法) for j←2 to n do将A(j)放入已分类集合A(1:j−1) repeat4.4归并分类 问题描述:给定一个含有n个元素的集合,把它们按一定的次序分类(如非降次序)
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分:平均分为2个子集合治:递归调用分类算法,将2个子集合分类合:将2个分类的子集合并为一个分类集合4.4归并分类分治策略设计归并分类算法
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的算法描述 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
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归并分类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归并分类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归并分类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
43
44
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数组的归并函数 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(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(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归并分类
494.4归并分类讨论:1.可以消去递归,取消栈的使用,例如:①采用由底向上的方法,将元素两两配对;
②自然合并排序法;
2.空间代价3.适合于并行计算,采用并行或专用集成电路实现数据排序操作时,派生出许多算法,例如奇偶合并排序,双调合并排序等。
(8)(7)(6)(5)(4)(3)(2)(1)5535701530251050
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)表示一次比较一种可能的分类序列
544.5快速分类
554.5快速分类
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返回划分元素的下标递归调用划分之后得到的两个集合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首先调用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]8972135594.5快速分类A[m]=A[p];
即A[1]=A[4]=2A[p]=t;
即A[4]=5end
60•快速分类算法的分析I:时间复杂性假设前提互不相同;
随机选取划分元素划分单元随机选取的改进快速分类的性能取决于划分的对称性!随机选取更合理,因为最好能找到中间元素最坏情况下:划分算法比较次数为元素数:p-m+1第i级的比较次数:n-i+1 (实际上是固定的)最坏情况下级数为n-1(每次取最小或最大值)总和:n+(n-1)+…= O(n2)平均情况下:划分元素最终位置机会均等,运用概率公式得:
61•快速分类算法的分析II:栈空间使用递归算法:最坏情况下O(n)改进的迭代算法:每次选择小的文件继续处理(较小的文件在处理过程中相对迭代次数少,可能产生的栈空间占用少)O(log n)归并分类和快速分类算法的比较
62•选择问题定义•算法2.15•举例•分析:最坏情况下:O(n2)平均情况下:O(n)4.6选择问题
63
64•构造最坏情况下O(n)的选择算法•二次中间值规则•粗略算法2.16•分析•Select2的实现
66将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。
由此可将方程C=AB重写为:1969年,Strassen采用分治法:由此可得:复杂度分析4.7Strassen矩阵乘法
68
69小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}