第二部分算法设计方案与分析的基本方法及技巧.PPT
《第二部分算法设计方案与分析的基本方法及技巧.PPT》由会员分享,可在线阅读,更多相关《第二部分算法设计方案与分析的基本方法及技巧.PPT(45页珍藏版)》请在三一文库上搜索。
1、第二章 算法设计与分析的基本方法及技巧,2.1 程序运行时间 2.2 一类递归方程的求解 2.3 分治 2.4 平衡 2.5 贪心法 2.6 动态规则 2.7 回溯,算法(Algorithm):是对特定问题求解步骤的一种描述,它是 指令(规则)的有限序列,其中每一条指令表示一个或多个操作。,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。,Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn M
2、s al-Khowrizm (约公元前825年) 从字面上看,这个名字的意思是“Jafar 的父亲,Mohammed 和 Ms 的儿子,Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发) 的小城镇 。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala (复原和化简的规则);,资料:Algorithm与Logarithm 这个词一直到1957年之前在Websters New World Dictionary(韦氏新世界词典)中还未出现,我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术),指的是用阿拉伯数字进行算术运算的过
3、程。在中世纪时,珠算家用算盘进行计算,而算术家用算术进行计算。中世纪之后,对这个词的起源已经拿不准了,早期的语言学家试图推断它的来历,认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的,但另一些人则不同意这种说法,认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后,数学史学家发现了algorism(算术)一词的真实起源:它来源于著名的Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm (约公元前825年)从字面上看,这个名字的意思是“Jafar 的父亲,Mohammed 和 M
4、s 的儿子,Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发) 的小城镇 。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala (复原和化简的规则);另一个词,“algebra”(代数),是从他的书的标题引出来的,尽管这本书实际上根本不是讲代数的。 逐渐地,“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的,这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (数
5、学大全辞典) ,给出了Algorithmus (算法)一词的如下定义:“在这个名称之下,组合了四种类型的算术计算的概念,即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ,在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。 1950年左右,algorithm一词经常地同欧几里德算法(Euclids algorithm)联系在一起。这个算法就是在欧几里德的几何原本(Euclids Elements ,第VII卷,命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。,递归技术 最常用的算法设
6、计思想,体现于许多优秀算法之中 分治法 分而制之的算法思想,体现了一分为二的哲学思想 模拟法 用计算机模拟实际场景,经常用于与概率有关的问题 贪心算法 采用贪心策略的算法设计 状态空间搜索法 被称为“万能算法”的算法设计策略 随机算法 利用随机选择自适应地决定优先搜索的方向 动态规划 常用的最优化问题解决方法,“好”的算法的标准: 正确性,算法能满足具体问题的需求 可读性,首先方便阅读与交流,其次才是机器执行 健壮性,输入错误时,能作出反应,避免异常出错 效率与低存储量要求,算法的特征: 有穷性、确定性、输入、输出、能行性,对算法“正确性”的要求: 不含语法错误; 对于几组输入数据能得到满足要
7、求的结果; 对精心选择苛刻并带有刁难的数据能得到满足要求的结果; 对于一切合法的输入均得到满足要求的结果;,算法描述: 自然语言;程序设计语言;类语言*;,关于本书采用的类语言描述: 结构类型说明 输入输出约定( cin v , cout v ) new 和 delete 引入引用类型 其他,影响算法执行的因素: 算法实现后所消耗的时间* 算法实现后所占存储空间的大小* 算法是否易读、易移植等等其它问题,影响时间特性的四个因素: 程序运行时输入数据的总量 对源程序编译所需的时间 计算机执行每条指令所需的时间 程序中指令重复执行的次数*,定义 语句频度:语句重复执行的次数,程序运行时间,渐近时间
8、复杂度(时间复杂度)T(n),算法中基本操作重复执行的次数是问题规模n的某个函数 f(n),算法的时间度量记作: T(n)= O( f(n) 它表示随问题规模n的增大,算法执行时间的增长率和 f(n)的增长率相同。,渐近空间复杂度(空间复杂度)S(n),S(n)= O( g(n),运算法则: 设:T1(n)=O( f(n) ),T2(n)=O( g(n) ) 加法规则:T1(n)+T2(n) = O( max f(n), g(n) ) 乘法规则:T1(n) T2(n) = O( f(n) g(n) ),设:,T(x) : 取变量或常量x之值所消耗时间 T(.V): 取变量V之地址所消耗的时间
9、T(=) : 赋值所消耗时间 T() : 执行基本运算所耗时间 T(call/return):执行函数调用和返回所耗时间 T(par) : 将参数par传给函数所消耗时间,(1) 表达式和赋值语句 exp:=常数 | 变量 | F-name(e1,e2,em) | (exp exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T()+T(exp) T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body) 例: T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相应的汇编程序为: l
10、oad a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2,通常取O(1),(2) 语句序列 T(s1,s2,sk)=maxT(s1),T(s2),T(sk) (3) 条件语句 T( if (B) s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 通常取T(B)+T(else)=O(1) T(if(B) s )=O(1)+T(s) (4) Switch语句 设语句s switch(E) case E1: S1; case Ek: Sk; default : Sm T(s)=T(E)+T(Ei
11、)+maxT(s1),T(sk),T(sm) O(1),k i=1,(5) for语句 T( for(i=1;i=n;i+) s ) =(T(s)+T(i=1)+T(i=n)+T(i+)+T(for),O(1),(6) while语句 while(B) s i=0;while(B) s ; i+ 设RT0表示某一次循环开始执行时的绝对时间 关于循环的定时不变式RT为 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中:T(while)代表测试循环终止条件所耗时间 T(j)代表跳回循环头所耗时间 可简化成:T(j)=T(while) T(while(B)s)=RT
12、-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while),(7) 函数调用 递归调用:被调用子函数运行时间 非递归调用:求解递归方程 (8) goto语句 goto语句破坏了程序结构 一般对goto语句限制使用 对有条件的goto转移可忽略不计,Void BUBBLE(A) int An; int I,j,temp; for(i=0;i=i+1;j-) O(n-i-1) if(Aj-1Aj) O(n-i-1) 1) O(n(n-1)/2) temp=Aj-1; O(1) O(1) =(n-i-1) =O(n2) Aj-1=Aj; O(1) O(1) Aj=temp; O(1) ,
13、n-2 i=0,举例: s = 0 ; f(n) = 1; T1(n) = O(f(n) = O(1) 常量阶 for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T2(n) = O(f(n) = O(n) 线性阶 for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方阶 for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ;
14、 k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方阶,举例: Long fact ( int n) if ( n=0 ) | ( n =1 ) return( 1 ); else return( n * fact( n 1 ) ); ,f( n ) = n G T( n ) = O( f( n ) ) = O( n ),int sort(i,j) int i,j; if(i=j) return(xi); else m=(i+j-1)/2; return(merge(sort(i,m),so
15、rt(m+1),j); ,这是一个快速排序算法 merge的运行时间正比于n(n是2的幂) 设T(n)是sort最差情况下的运行时间,则,一类递归方程的求解,猜解法: 首先猜出一个解f(n)的形式,令其带有待定参数;在归纳 推理过程中确定待定参数,并利用方程证明T(n) f(n)。 若推理过程能够完成且待定参数能够确定,则求解完毕。 f(n)可以是 O(1) , O(n) , O(nlogn) , O(n2)等等。,猜测1:对参数a,T(n) anlogn,带入n=1,由于anlogn=0 虽然满足T(1) c1,但它与a无关,无法确定a与c1关系。 此猜测失败。,猜测2:T(n)=anlog
16、n+b,当n=1时,只要bc1即可。 当n2时,设对所有的 kn 有 T(k) aklogk+b 令k=n/2 得 T(n/2) a(n/2)log(n/2)+b 带入原式: T(n) 2T(n/2)+c2n2(a(n/2)log(n/2)+b)+c2n =an(logn-1)+c2n+2b =anlogn+b-(an-c2n-b) 只要令an-c2n-b0就有 T(n) anlogn+b 选择ac2+b,使an-c2n-b0得到满足。 使T(n) anlogn+b成立的两个约束是: bc1,ac2+b 取b=c1 , a=c1+c2 是合理的。,一类递归方程的展开式与通解,设T(n)是求解某
17、个问题的时间开销,n使问题的数据量。设计 对此问题列出的递归方程为: T(1)=1 T(n)=aT(n/c)+d(n) n2 其中c是大于等于1的正整数。全部数据被分割成c等分,每分的 数量为n/c。T(n/c)是求解一个子问题的时间开销。aT(n/c)代表求 解a个问题的时间开销。D(n)是任意的函数,方程是严格的等式。 用n/ci代替n得: T(n/ci)=aT(n/ci+1)+d(n/ci), i=1,2,3, T(n)=aT(n/c)+d(n) =a(aT(n/c2)+d(n/c)+d(n)=a2T(n/c2)+ad(n/c)+dn =a2(aT(n/c3)+d(n/c2)+ad(n/
18、c)+d(n) =a3T(n/c3)+a2d(n/c2)+ad(n/c)+d(n) = =ai T(n/ci)+ajd(n/cj),i-1 j=0,倍积函数:若对所有的正整数x,y,有f(xy)=f(x)f(y),则 f 是 正整数上的倍积函数。 若d(n)是倍积函数。则有: d(ck-1)=(d(c)k-1,定理:设a,c是非负常数,n是2的幂,d(n)是倍积函数,则,的齐次解是O(nlogc ),且对特解有如下结论: (1)若ad(c),则特解是O(ak),或O(nlogc ),即特解与齐次解同阶 (2)若ad(c),则特解是O(d(c)k),或O(nlogcd(c)即特解与d同阶 (3)
19、若a=d(c),则特解是齐次解的logcn。,a,a,基本思想:分而治之。将一个规模为n的问题分解为k个规模较小 的子问题,这些子问题互相独立且与原问题相同。递 归地解这些子问题,然后将各子问题的解合并得到原 问题的解。,设问题输入数据A0n-1,函数dac(p,q)求子问题Ap,q的解。 对函数dac的首次调用是dac(0,n-1)。,int dac(int p, int q) if(small(p,q) return(G(p,q); else (m1,mk)=divide(p,q); return(Combine(dac(p,m1),dac(m1+1,m2), ,dac(mk+1,q);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 部分 算法 设计方案 分析 基本 方法 技巧
链接地址:https://www.31doc.com/p-3215573.html