1 第二章算法设计与 分析的基本方法及 技巧 主讲.pdf
( 4.5 )《1 第二章算法设计与 分析的基本方法及 技巧 主讲.pdf》由会员分享，可在线阅读，更多相关《1 第二章算法设计与 分析的基本方法及 技巧 主讲.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1第二章 算法设计与分析的基本方法及技巧主讲人：单丽莉2003年8月2005-2ITNLP Lily Shan 2第二章 算法设计与分析的基本方法及技巧第二章 算法设计与分析的基本方法及技巧2.1 算法定义及描述2.2 算法性能分析2.2.1 算法性能要求2.2.2 算法的执行时间2.2.3 一类递归方程的求解2.2.4 算法的空间复杂度分析2.3 常用算法设计策略2005-2ITNLP Lily Shan 32.1算法定义及描述算法定义及描述?算法：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列算法：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列?算法的特性：
2、算法的特性：?输入有0个或多个输入输入有0个或多个输入?输出有一个或多个输出(处理结果)输出有一个或多个输出(处理结果)?确定性每步定义都是确切、无歧义的确定性每步定义都是确切、无歧义的?有穷性算法应在执行有穷步后结束有穷性算法应在执行有穷步后结束?有效性有效性算法中的每个操作都可以通过已经实现的基本运算执行有限次来实现的，而且人们用纸和笔作有穷次即可完成。算法中的每个操作都可以通过已经实现的基本运算执行有限次来实现的，而且人们用纸和笔作有穷次即可完成。2005-2ITNLP Lily Shan 42.1算法定义及描述算法定义及描述(续续)?算法设计原则算法设计原则：自上而下，逐步求精。?算法
3、的描述算法的描述：伪语言；C+；类C语言格式：算法：名称输入：数据说明输出：数据说明 。/操作序列2005-2ITNLP Lily Shan 52.1算法定义及描述算法定义及描述(续续)【例2.1】将一个数字序列排序为非降序。算法：数字序列排序输入：数字序列a1,a2,an。输出：输出序列的一个枚举a1,a2,，an使得a1a2a3。/具体操作伪代码2005-2ITNLP Lily Shan 62.2 算法性能分析算法性能分析2.2.1 算法性能要求2.2.2 算法的执行时间2.2.3 一类递归方程的求解2.2.4 算法的空间复杂度分析22005-2ITNLP Lily Shan 72.2.1
4、 算法性能要求算法性能要求?算法性能要求算法性能要求1.正确性:算法应当满足具体问题的需求.2.可读性:有助于人对算法的理解;3.健壮性:当输入数据非法时,也能适当地作出反应或进行处理,而不会产生莫明其妙的输出结果;4.效率与低存储量需求:执行时间少,存储空间小.1.正确性:算法应当满足具体问题的需求.2.可读性:有助于人对算法的理解;3.健壮性:当输入数据非法时,也能适当地作出反应或进行处理,而不会产生莫明其妙的输出结果;4.效率与低存储量需求:执行时间少,存储空间小.2005-2ITNLP Lily Shan 82.2.1 算法性能要求(续)算法性能要求(续)?算法性能选择算法性能选择?一
5、个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。?我们只能根据具体情况有所侧重：若该程序使用次数较少，则力求算法简明易编写,易读,易调试和维护 对于反复多次使用的程序，应尽可能选用快速的算法；若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。2005-2ITNLP Lily Shan 92.2.2 算法的执行时间?算法执行的绝对时间算法执行的绝对时间(程序的运行时间程序的运行时间)?算法选用的策略算法选用的策略?问题的规模问题的规模?选用的程序语言选用的程序语言?编译程序产生的机器代码的质量编译程序产生的机器代码的质量?机器执行指令的速度机器执行指令的速
6、度2005-2ITNLP Lily Shan 102.2.2 算法的执行时间算法的执行时间(续续)?比较同一问题的不同算法比较同一问题的不同算法?撇开计算机软撇开计算机软,硬件因素硬件因素;?只考虑问题的规模对执行时间的影响只考虑问题的规模对执行时间的影响?以算法中基本操作执行时间为单位时间以算法中基本操作执行时间为单位时间;?以该基本操作重复执行的次数记为以该基本操作重复执行的次数记为f(n)(是问题规模是问题规模n的函数的函数)作为程序运行的时间量度作为程序运行的时间量度;?程序运行时间记为程序运行时间记为T(n)是问题规模是问题规模n的函数的函数;2005-2ITNLP Lily Sha
7、n 112.2.2 算法的执行时间(续)?程序的运行时间程序的运行时间f(n)的计算方法的计算方法?程序的运行时间程序的运行时间f(n)=程序中所有的语句的执行时间之和每条语句的执行时间=语句的执行频度(即次数(Frequency Count)语句执行一次所需时间,又假设每条语句执行一次所需的时间均是单位时间1(或等于基本操作时间)则=程序中所有的语句的执行时间之和每条语句的执行时间=语句的执行频度(即次数(Frequency Count)语句执行一次所需时间,又假设每条语句执行一次所需的时间均是单位时间1(或等于基本操作时间)则,f(n)=程序中所有语句的执行频度之和.程序中所有语句的执行频
8、度之和.122.2.2 算法的执行时间(续)【例2.1】设n为正整数.试确定下列各程序段中前置以记号的语句的执行频度.(1)i=1;k=0;While(i=n-1)k+=10*I;i+;(2)k=0;For(i=1;i=n;i+)for(j=I;j=n;j+)k+;(3)i=1;j=0;While(i+jj)j+;elsei+;(4)x=n;y=0;While(x=(y+1)*(y+1)y+;(1)n-1(2)(n+1)n/2(3)2/n32005-2ITNLP Lily Shan 132.2.2 算法的执行时间(续)【例2.2】求两个n阶方阵的乘积 C=AB,其算法如下:#define n
9、100/n 可根据需要定义可根据需要定义,这里假定为这里假定为100void MatrixMultiply(int Ann，int B nn，int Cnn)int i,j,k;(1)for(i=0;in;i+)(2)for(j=0;jn;j+)(3)Cij=0;(4)for(k=0;kn;k+)(5)Cij=Cij+Aik*Bkj;该算法中所有语句的频度之和该算法中所有语句的频度之和(即算法的时间耗费即算法的时间耗费)为：为：T(n)=2n3+3n2+2n+1(1.1)n+1n(n+1)n2n2(n+1)n32005-2ITNLP Lily Shan 142.2.2 算法的执行时间(续)?研
10、究程序的运行时间实质是研究研究程序的运行时间实质是研究T(n)的增长率的增长率,决定该算法在计算机上能解决多大规模的问题决定该算法在计算机上能解决多大规模的问题.?增长率的上界增长率的上界:存在一个常数存在一个常数C和整数和整数n0，当，当nn0时，程序运行时间时，程序运行时间T(n)Cf(n)，则称函数，则称函数f(n)是是(n)增长率的上界增长率的上界,记为记为T(n)(f(n)。?它表示随问题规模它表示随问题规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。的增长率相同，称作算法的渐进时间复杂度，简称时间复杂
11、度。?增长率的下界增长率的下界:存在一个常数存在一个常数C，使得对无穷多个，使得对无穷多个n，程序运行时间，程序运行时间T(n)Cg(n)，则函数，则函数g(n)是是(n)增长率的下界，记为增长率的下界，记为T(n)(g(n)。2005-2ITNLP Lily Shan 152.2.2 算法的执行时间(续)【例【例2.3】设函数】设函数T(n)=3n3+2n2,证明证明T(n)=O(n3),T(n)=(n3)取取n0=0,C=5,则当则当n0时有时有:T(n)=3n3+2n25n3另一方面另一方面,取取C=1,则当则当n=0,1,2,有有T(n)=3n3+2n2n32005-2ITNLP Li
12、ly Shan 162.2.2 算法的执行时间(续)?如何评价一个程序的运行时间如何评价一个程序的运行时间:?评价一个程序的运行时间，是在程序解决的问题规模发生变化时，看程序运行时间的增长率即时间复杂度。增长率越慢，其时间复杂性越好。评价一个程序的运行时间，是在程序解决的问题规模发生变化时，看程序运行时间的增长率即时间复杂度。增长率越慢，其时间复杂性越好。?讨论程序的时间复杂度时，由定义可知我们只要关心算法中执行频度最大的句子的时间复杂度就足够了。讨论程序的时间复杂度时，由定义可知我们只要关心算法中执行频度最大的句子的时间复杂度就足够了。?如果程序的运行时间不随着问题规模n的增加而增长，即使算
13、法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度仍是如果程序的运行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度仍是O(1)。(1)。2005-2ITNLP Lily Shan 172.2.2 算法的执行时间(续)【例2.4】变量计数之一。变量计数之一。(1)x=0;y=0;(2)for(k=1;k=n;k+)(3)x+;(4)for(i=1;i=n;i+)(5)for(j=1;j=n;j+)(6)y+;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成
14、分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。2005-2ITNLP Lily Shan 182.2.2 算法的执行时间(续)【例【例2.5】变量计数之二。】变量计数之二。(1)x=1;(2)for(i=1;i=n;i+)(3)for(j=1;j=i;j+)(4)for(k=1;k=j;k+)(5)x+;该程序段中频度最大的语句是
15、(5)，语句(5)的执行次数：该程序段中频度最大的语句是(5)，语句(5)的执行次数：()()(2/)1(216/)12)(1(21212122)1(1311212111111nOnnnnniiiiiijnininininiijniijjk=+=+=+=+=42005-2ITNLP Lily Shan 192.2.2 算法的执行时间(续)?复合结构的程序运行时间复杂度计算规则复合结构的程序运行时间复杂度计算规则顺序结构的计算原则顺序结构的计算原则加法规则：设加法规则：设T1(n)=O(f(n)和和T2(n)=O(g(n)是程序段是程序段P1和和P2的运行时间的运行时间,P1和和P2是顺序执行结
16、构是顺序执行结构,则执行则执行P1和和P2的程序运行时间为：的程序运行时间为：T1(n)+T2(n)因而其时间复杂性为：因而其时间复杂性为：O(max(f(n),g(n)2005-2ITNLP Lily Shan 202.2.2 算法的执行时间(续)?复合结构的程序运行时间复杂度计算规则复合结构的程序运行时间复杂度计算规则2.循环结构的计算原则循环结构的计算原则乘法规则：设乘法规则：设T1(n)=O(f(n)和和T2(n)=O(g(n)是程序段是程序段P1和和P2的运行时间，的运行时间，P1和和P2是包含关系的循环执行结构，则执行是包含关系的循环执行结构，则执行P1和和P2的程序运行时间为：的
17、程序运行时间为：T1(n)*T2(n)因而其时间复杂性为：因而其时间复杂性为：O(f(n)*g(n)2005-2ITNLP Lily Shan 212.2.2 算法的执行时间(续)【例2.6】变量计数之一。变量计数之一。(1)x=0;y=0;(2)for(k=1;k=n;k+)(3)x+;(4)for(i=1;i=n;i+)(5)for(j=1;j=0&(Ai!=k)(3)i-;(4)return i;此算法中的语句此算法中的语句(3)的频度不仅与问题规模的频度不仅与问题规模n有关，还与输入实例中有关，还与输入实例中A的各元素取值及的各元素取值及K的取值有关的取值有关:若若A中没有与中没有与K
18、相等的元素，则语句相等的元素，则语句(3)的频度的频度f(n)=n；若；若A的最后一个元素等于的最后一个元素等于K,则语句则语句(3)的频度的频度f(n)是常数是常数0。2005-2ITNLP Lily Shan 232.2.2 算法的执行时间(续)?最坏时间复杂度和平均时间复杂度最坏时间复杂度和平均时间复杂度?最坏时间复杂度:最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比它更长。最坏时间复杂度:最坏情况下的时间复杂度称最坏时间复杂度。
19、一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比它更长。?平均时间复杂度平均时间复杂度:是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。需考虑不同情况进行代价分析。是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。需考虑不同情况进行代价分析。242.2.2 算法的执行时间(续)【例【例2.7】在数值】在数值A0.n-1中查找给定值中查找给定值K的算法大致如下：的算法大致如下：(1)i=n-1;(2)while(i=0&(Ai!=k)(3)i-;
20、(4)return i;最坏时间复杂度最坏时间复杂度:T(n)=O(n)平均时间复杂度平均时间复杂度:假设查找成功和不成功的可能性各占假设查找成功和不成功的可能性各占1/2则则()nOnnOninOnTni=+=+=24121121)(152005-2ITNLP Lily Shan 252.2.2 算法的执行时间(续)常数阶对数阶线性阶线性对数阶平方阶常数阶对数阶线性阶线性对数阶平方阶)1(常见的时间复杂度，按数量级递增排序：常见的时间复杂度，按数量级递增排序：)n(log2)n()nlogn(2)n(2)n(3)n(k)2(n立方阶立方阶K次方阶指数阶K次方阶指数阶2005-2ITNLP L
21、ily Shan 262.2.2 算法的执行时间(续)【例【例2.8】按增长率由小至大的顺序排列下列各函数】按增长率由小至大的顺序排列下列各函数:2100,(3/2)n,(2/3)n,(4/3)n,nn,n3/2,n2/3,n,log(n),(log(n)2,log(logn),nlog(n),nlogn.答答:(2/3)n2100log(logn),log(n),(log(n)2,n2/3n,nlog(n),n3/2(4/3)n (3/2)n nlognnn,nn2005-2ITNLP Lily Shan 27?递归函数中时间复杂度分析【例递归函数中时间复杂度分析【例2.13】计算】计算N！
22、的递归函数！的递归函数 FACT(n)如下：如下：Int FACT(int n)if (n=1)return 1;else return(n*FACT(n-1);分析时间代价：设分析时间代价：设 T(n)是是 FACT(n)的时间代价函数的时间代价函数2.2.3 一类递归方程的求解一类递归方程的求解D=O(1)(n1)其中C、D为常数2005-2ITNLP Lily Shan 28?递归函数中时间复杂性：递归方程的求解递归函数中时间复杂性：递归方程的求解当当n1时，需求解出代价函数时，需求解出代价函数T(n);还有：还有：T(n)=2T(n/2)+(n)T(n)=2T(n/2)+(n)2.2.
23、3 一类递归方程的求解一类递归方程的求解(续续)O(1)(n1)T nTnn()=+22()T nTnn()=+932005-2ITNLP Lily Shan 29?递归方程的求解方法递归方程的求解方法?猜解法：猜解法：?根据已知的阶如根据已知的阶如O(nlogn),O(n2)，猜一个类似的，猜一个类似的T(n)；?利用数学归纳法或其它方法证明正确性。利用数学归纳法或其它方法证明正确性。?代入展开：代入展开：?循环地展开递归方程，把递归方程转化为和式循环地展开递归方程，把递归方程转化为和式?然后可使用求和技术解之。然后可使用求和技术解之。?使用使用Master定理定理?求解型方程,是常数，是正
24、函数求解型方程,是常数，是正函数2.2.3 一类递归方程的求解一类递归方程的求解(续续)()()(nfbnaTnT+=0b,1af n()2005-2ITNLP Lily Shan 30?猜解方法猜解方法【例2.14】求解【例2.14】求解,T(1)=1.解：解：(1)展开展开T(n)若干步若干步,可以猜测可以猜测T(n)=O(nlogn).(2)用归纳法证明用归纳法证明T(n)=O(nlogn).当当n=2时时,T(2)=2*T(1)+2=4,令令T(2)C*2log2,只要取只要取C2当当n2 时时,对所有的对所有的n令令T(n)Cnlogn往证：存在往证：存在C使得使得T(n)Cnlog
25、n2.2.3 一类递归方程的求解一类递归方程的求解(续续)T nTnn()=+2262005-2ITNLP Lily Shan 31【例2.14】求解【例2.14】求解,T(1)=1.只要取只要取C 1,即有即有T(n)Cnlogn所以有当所以有当n0=2,C2时时,对所有的对所有的nn0,都有都有T(n)Cnlogn,即即T(n)=O(nlogn)2.2.3 一类递归方程的求解一类递归方程的求解(续续)T nTnn()=+22nnnCnnTnT+=)2log2(2)2(2)()nnnCnT+)2log()log(22)(nnCnnCnT+log)()1(log)(CnnnCnT2005-2I
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 第二章算法设计与 分析的基本方法及 技巧 主讲 第二 算法 设计 分析 基本 方法
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内