2第二章 算法效率分析基础.pptx

《2第二章 算法效率分析基础.pptx》由会员分享，可在线阅读，更多相关《2第二章 算法效率分析基础.pptx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计 Analysis and Design of Computer Algorithms 第二章 算法效率分析基础杨春明西南科学技大学计算机学院Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 2算法效率分析基础l算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。Time is Important不是所有能计算的都有价值，不是所有有价值的都能被计算不是所有能计

2、算的都有价值，不是所有有价值的都能被计算 阿尔伯特.爱因斯坦Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 3教学内容l算法效率分析框架l算法效率的表示符号l非递归算法的效率分析l递归算法的效率分析l算法的经验分析l要求掌握算法中近似时间的表示、非递归、递归算法的效率分析方法，了解算法的经验分析Analysis and Design of Computer AlgorithmsA

3、nalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 4分析框架输入规模度量l输入规模度量算法的时间效率和空间效率都用输入规模的函数进行度量。对于所有的算法，对于规模更大的输入都需要运行更长的时间。经常使用一个输入规模n为参数的函数来研究算法的效率。选择输入规模的合适量度，要受到所讨论算法的操作细节影响。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms

4、 School of Computer Science and Technology,SWUST 5分析框架运行时间的度量单位l运行时间的度量单位用算法的基本操作（算法中最重要的操作）基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。基本操作基本操作通常是算法最内层循环中最费时的操作。算法运行时间的估计：T(n)copC(n)n是该算法的输入规模cop是特定计算机上一个算法基本操作的执行时间C(n)是该算法需要执行的基本操作的次数Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Alg

5、orithms School of Computer Science and Technology,SWUST 6分析框架增长次数l增长次数小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来。一个需要指数级操作次数的算法只能用来解决规模非常小的问题一个需要指数级操作次数的算法只能用来解决规模非常小的问题Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 7分析框架算法

6、的最优、最差和平均效率l算法的最优、最差和平均效率最差效率最差效率是指在输入规模为n时，算法在最坏情况下的效率。最优效率最优效率是指在输入规模为n是，算法在最优情况下的效率。平均效率平均效率是指在“典型”或“随机”输入的情况下，算法具有的行为（效率）。摊销效率摊销效率是指对于同样的数据结构执行多次操作，然后分摊到每一次上。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 8渐进符号

7、l算法效率的主要指标是基本操作次数的增长增长次数次数。l为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：O（读“O”）：上界（读”omega”）：下界（读”theta”）：近似Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 9符号Ol定义1 对于足够大的n，t(n)的上界由g(n)的常数倍来确定，即：l记为t(n)O(g(n)t(n)cg(n)，c为常数n O(n

8、2)100n+5 O(n2)n(n-1)/2 O(n2)Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 10符号l定义2 对于足够大的n，t(n)的下界由g(n)的常数倍来确定，即：l记为t(n)(g(n)t(n)cg(n)，c为常数n3(n2)n(n+1)(n2)4n2+5 (n2)Analysis and Design of Computer AlgorithmsAnalys

9、is and Design of Computer Algorithms School of Computer Science and Technology,SWUST 11符号l定义3 对于足够大的n，t(n)的上界和下界由g(n)的常数倍来确定，即：l记为t(n)(g(n)c2g(n)t(n)c1g(n)，c1,c2为常数n2+3n+2(n2)n(n-1)/2(n2)4n2+5 (n2)Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer

10、 Science and Technology,SWUST 12渐进符号的有用特性l定理 如果t1(n)O(g1(n)并且t2(n)O(g2(n)，则 t1(n)+t2(n)O(max(g1(n),g2(n)l对于符号和，该定理也成立。l该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 1

11、3利用极限比较增长次数前两种情况意味着t(n)O(g(n)后两种情况意味着t(n)(g(n)第二种情况意味着t(n)(g(n)Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 14基本的效率类型常量(1)、对数(logn)、线性(n)、nlogn、平方(n2)、立方(n3)、指数(2n)、阶乘(n!)Analysis and Design of Computer Algorithm

12、sAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 15非递归算法的数学分析lExample 1：讨论下面这个算法（从n个元素中查找最大元素问题）的效率。算法算法 MaxElement(A0.n-1/求给定数组中的最大元素/输入：实数数组A0.n-1/输出：A中的最大元素maxval A0for i 1 to n-1 do if Ai maxval maxval Aireturn maxval 考虑：1.循环中的操作有比较比较和赋值赋值，取哪一个作为基本操作？2.

13、输入规模是多少？基本操作为：比较运算输入规模就是数组长度n算法的效率为：Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 16分析非递归算法效率的通用方案1.决定用那些参数作为输入规模的度量。2.找出算法的基本操作。3.检查基本操作的执行次数是否只依赖输入规模。4.建立一个算法基本操作执行次数的求和表达式。5.利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它

14、的增长次数。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 17Example 考虑下面算法的效率lExample 2 元素唯一性问题元素唯一性问题算法算法 UniqueElements(A0.n-1)/验证给定数组的元素是否全部唯一/输入：实数数组A0.n-1/输出：如果唯一，返回True，否则Falsefor i0 to n-2 do for ji+1 to n-1 do i

15、f Ai=Aj return Falsereturn True lExample 3 两个两个n阶方阵乘法阶方阵乘法算法算法 MatrixMuti(A0.n-1,0.n-1,B0.n-1,0.n-1)/根据定义计算两个n阶矩阵的乘积/输入：两个n阶矩阵/输出：矩阵C=ABfor i0 to n-1 do for j0 to n-1 do Ci,j 0.0 for k 0 to n-1 do Ci,j=Ci,j+Ai,k*B k,jreturn C Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer

16、Algorithms School of Computer Science and Technology,SWUST 18递归算法的数学分析l例：对于任意非负整数n，计算F(n)=n!的值。F(n)=n(n-1)!,n11 ,n=11 ,n=0算法 F(n)/递归计算n!/输入：非负整数n/输出：n!的值if n=0 retuen 1else return F(n-1)*nM(n)=M(n-1)+1 ,n10 ,n=0M(n)=M(n-1)+1 =M(n-2)+1+1=M(n-2)+2 =M(n-3)+1+2=M(n-3)+3 =M(n-n)+1+n-1=nAnalysis and Desig

17、n of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 19分析递归算法效率的通用方案l决定用哪个参数作为输入规模的度量l找出算法的基本操作l检查对相同规模的输入，基本操作的执行次数是否相同，如果不同，必须对最差、平均及最优效率单独研究l建立一个递推关系式及相应的初始条件l求解这个递归关系式，或者至少确定解的增长次数Analysis and Design of Computer AlgorithmsAnalysis and

18、 Design of Computer Algorithms School of Computer Science and Technology,SWUST 20汉诺塔M(n)=2M(n-1)+1 ,n11 ,n=1M(n)=2n-1我们应该谨慎使用递归算法，因为他们的简洁可能会掩盖他们的低效率。我们应该谨慎使用递归算法，因为他们的简洁可能会掩盖他们的低效率。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Tec

19、hnology,SWUST 21斐波那契数列F(n)=F(n-1)+F(n-2),n11 ,n=10 ,n=00,1,1,2,3,5,8,13,21,34,Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 22算法的经验分析l对算法效率做经验分析的通用方案了解试验的目的决定用来度量效率的量度M和度量单位（单位时间内的操作次数）决定输入样本的特性为实验准备算法的程序实现生成输入样本对

20、输入样本进行计算，并记录观察到的实验数据分析获得的实验数据Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 23Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 24算

21、法可视法l通过使用图形来传达关于算法的一些有用信息。l算法可视法的种类：静态算法可视法动态算法可视法(算法动画,Algorithm Animation)Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 25静态算法可视法Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorith

22、ms School of Computer Science and Technology,SWUST 26静态算法可视法Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Computer Science and Technology,SWUST 27动态算法可视法Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms School of Com

23、puter Science and Technology,SWUST 28小结l算法效率包括时间效率和空间效率。l时间效率主要用它的输入规模的函数来度量，该函数计算算法基本操作的执行次数。l最差、最优与平均效率l增长次数l符号O，l非递归算法和递归算法的效率分析l递归算法简洁性可能会掩盖它的低效率l算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析观测到的数据。Analysis and Design of Computer AlgorithmsAnalysis and Design of Computer Algorithms9、静夜四无邻，荒居旧业贫。12月-2312月-23

24、Saturday,December 2,202310、雨中黄叶树，灯下白头人。10:49:3110:49:3110:4912/2/2023 10:49:31 AM11、以我独沈久，愧君相见频。12月-2310:49:3110:49Dec-2302-Dec-2312、故人江海别，几度隔山川。10:49:3110:49:3110:49Saturday,December 2,202313、乍见翻疑梦，相悲各问年。12月-2312月-2310:49:3110:49:31December 2,202314、他乡生白发，旧国见青山。02 十二月 202310:49:31 上午10:49:3112月-231

25、5、比不了得就不比，得不到的就不要。十二月 2310:49 上午12月-2310:49December 2,202316、行动出成果，工作出财富。2023/12/2 10:49:3110:49:3102 December 202317、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。10:49:31 上午10:49 上午10:49:3112月-239、没有失败，只有暂时停止成功！。12月-2312月-23Saturday,December 2,202310、很多事情努力了未必有结果，但是不努力却什么改变也没有。10:49:3110:49:3110:4912/2/2023 10

26、:49:31 AM11、成功就是日复一日那一点点小小努力的积累。12月-2310:49:3110:49Dec-2302-Dec-2312、世间成事，不求其绝对圆满，留一份不足，可得无限完美。10:49:3110:49:3110:49Saturday,December 2,202313、不知香积寺，数里入云峰。12月-2312月-2310:49:3110:49:31December 2,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。02 十二月 202310:49:31 上午10:49:3112月-2315、楚塞三湘接，荆门九派通。十二月 2310:49 上午12月-2310:4

27、9December 2,202316、少年十五二十时，步行夺得胡马骑。2023/12/2 10:49:3110:49:3102 December 202317、空山新雨后，天气晚来秋。10:49:31 上午10:49 上午10:49:3112月-239、杨柳散和风，青山澹吾虑。12月-2312月-23Saturday,December 2,202310、阅读一切好书如同和过去最杰出的人谈话。10:49:3110:49:3110:4912/2/2023 10:49:31 AM11、越是没有本领的就越加自命不凡。12月-2310:49:3110:49Dec-2302-Dec-2312、越是无能的人

28、，越喜欢挑剔别人的错儿。10:49:3110:49:3110:49Saturday,December 2,202313、知人者智，自知者明。胜人者有力，自胜者强。12月-2312月-2310:49:3110:49:31December 2,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。02 十二月 202310:49:31 上午10:49:3112月-2315、最具挑战性的挑战莫过于提升自我。十二月 2310:49 上午12月-2310:49December 2,202316、业余生活要有意义，不要越轨。2023/12/2 10:49:3110:49:3102 December 202317、一个人即使已登上顶峰，也仍要自强不息。10:49:31 上午10:49 上午10:49:3112月-23MOMODA POWERPOINTLorem ipsum dolor sit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis amet,consectetur adipiscing elit.Fusce id urna blanditut cursus.感感 谢谢 您您 的的 下下 载载 观观 看看专家告诉