电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本
换一换
首页 金锄头文库 > 资源分类 > PPT文档下载
分享到微信 分享到微博 分享到QQ空间

算法2_算法分析基础

  • 资源ID:26280663       资源大小:1.14MB        全文页数:72页
  • 资源格式: PPT        下载积分:10金贝
快捷下载 游客一键下载
账号登录下载
微信登录下载
三方登录下载: 微信开放平台登录   支付宝登录   QQ登录  
二维码
微信扫一扫登录
下载资源需要10金贝
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

 
账号:
密码:
验证码:   换一换
  忘记密码?
    
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
下载须知 | 常见问题汇总

算法2_算法分析基础

第2章 算法分析基础,学习要点:掌握算法分析中的算法复杂度概念时间复杂度、空间复杂度最好、最坏和平均情况时间复杂度掌握算法分析的渐近表示法掌握用C+语言描述算法的方法章节内容:2.1 算法复杂度2.2 渐近表示法2.3 递推关系(课外阅读),2.1 算法复杂度,好算法的4个重要特征:Correctness正确性,注意区分“正确性”和“健壮性”的概念:算法正确性在合法的输入下,算法应实现预先规定的功能和计算精度要求。程序健壮性当输入不合法的数据时,程序应能做适当处理而不至于引起严重后果。正确性和健壮性互相补充。程序可靠性在正常情况下能正确地工作,在异常情况下也能做出适当处理。,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性,遗憾的是,简单的算法不一定高效,思路清晰、层次分明、容易理解、利于编码和调试。,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性Amount of time/space used效率,执行算法所需的时间和存储空间,算法设计者常常需要在算法的简明性和效率之间作出谨慎的选择,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性Amount of time/space used效率Optimality最优性,算法执行时间达到求解该类问题所需时间的下界。,与所求解问题自身的复杂程度有关。,For problem P, the algorithm A does at most WA(n) steps in the worst case (upper bound)F is a lower bound for a class of algorithm. (lower bound) If WA=F, then A is optimal.,Definition of the optimal algorithm(最优算法),means that: For any algorithm in the class, and any input of size n, there is some input of size n for which the algorithm must perform at least F(n) basic operations.,又如:可证排序问题的时间复杂度下界为(nlogn)。则最坏时间复杂性为O(nlogn)的排序算法是最优算法。因此:堆排序算法和两路合并排序算法都是最优算法。,例如:FindMax(int L) /求n个元素中的最大元素 int max=L0; int i=1; while(i<n) if (max<Li) max=Li; i=i+1; ,最优算法,影响程序运行时间的因素,程序所依赖的算法问题规模和输入数据计算机系统性能,根本的、起决定作用的,数值大小和状态,硬件系统性能(CPU速度)和软件系统性能(操作系统、编译器),输入、输出,运行一个算法所需的时间和空间资源的量。算法的时间复杂性(Time Complexity)T(n)算法的空间复杂性(Space Complexity)S(n) 其中n是问题的规模(输入大小),算法复杂度,How to Measure? Machine independentLanguage independentProgramming style independentImplementation independent,算法的时间复杂度,算法的时间复杂度算法运行所需的时间最好、最坏和平均时间复杂度,(不考虑计算机因素对算法分析的影响),最好情况(出现概率较大时分析)最差情况(实时系统)平均情况(已知输入数据是如何分布的,通常假设等概率分布),算法的时间复杂度,(1)最好情况下的时间复杂性:B(n) = Tmin(n) = min T(n,I) | IDn (2)最坏情况下的时间复杂性:W(n) = Tmax(n) = max T(n,I) | IDn (3)平均情况下的时间复杂性:A(n) = Tavg(n) =I:问题规模为n的实例。Dn :规模为n的所有合法输入的集合。p(I):实例I出现的概率。,算法的空间复杂度,算法的空间复杂度 算法运行所需的存储空间固定空间需求与所处理数据的大小和个数无关,即与问题实例的特征无关。(包括:程序代码、常量、简单变量、定长成分的结构变量所占的空间)可变空间需求与算法执行过程中处理的特定数据的规模有关。(如:数据元素所占的空间,算法执行所需的额外空间如递归算法所需系统栈空间),通过程序步来分析算法的时间复杂度,求数组元素累加之和的迭代程序:(P20 程序2-1)float Sum(float list,const int n) float tempsum=0.0;/1 for (int i=0;i<n;i+)/n+1 tempsum+=listi;/n return tempsum;/1,程序总步数为:2n+3,求数组元素累加之和的递归程序:(P21 程序2-2)float RSum(float list,const int n) if (n)/1 return RSum(list,n-1)+listn-1;/1 return 0;/1,程序总步数为:2n+2,但递归调用引起的循环计算和使用for语句的循环计算所需的开销是不同的。递归需要耗费更多的时间和空间资源。可见:程序步数并不能确切反映程序运行的实际时间。,2.2 渐近表示法,程序步的精确计算是困难的,且程序步并不能确切反映程序运行的实际时间。因此引入渐近时间复杂度,使用程序步在数量级上估计一个算法的执行时间,从而实现算法的事前分析。在数学上,算法的渐近复杂度t(n)是T(n) 的渐近表达式,是T(n)略去低阶项留下的主项,它比T(n) 简单。例如: T(n)=3n2+4nlogn+7 与t(n)= 3n2 当n时,有(T(n)-t(n)/T(n) 0。,那么在算法分析中呢?,渐近分析的记号:O、o、,在下面的讨论中,对所有n,f(n) 0,g(n) 0。 (1)渐近上界记号O如果存在正常数c和自然数n0,使得当n n0时有f(n) cg(n),则称函数f(n)当n充分大时有上界,且g(n)是它的一个上界,记做f(n)=O(g(n) 。即f(n)的阶不高于g(n)的阶。,上界记号O举例:C0=O(1)f(n)=C0为非零常数,取c=c0100n+6=O(n)取c=101, n0=66*2n+n2=O(n2)取c=7, n0=43log n+2*n+n2=O(n2)取c=6, n0=1,O(1)表示常数计算时间,代表算法只需执行有限个程序步。,如何证明?,证明 见P22,(定理2-1) 如果f(n)=amnm+am-1nm-1+a1n+a0是m次多项式,且am>0,则f(n)=O(nm)。,例如:程序2-1float Sum(float list,const int n) float tempsum=0.0;/1 for (int i=0;i<n;i+)/n+1 tempsum+=listi;/n return tempsum;/1,可以通过考察一个程序中关键操作(key operation)的执行次数,来估算算法的渐近时间复杂度。,关键操作!执行次数n和总的程序步2n+3有相同的渐近时间复杂度O(n)。,关键操作通常是位于算法最内层循环的程序步(或语句),是算法中执行次数最多的操作(程序步) 。,可以通过考察一个程序中关键操作(key operation)的执行次数,来估算算法的渐近时间复杂度。,关键操作通常是位于算法最内层循环的程序步(或语句),是算法中执行次数最多的操作(程序步) 。,例如:程序2-3 矩阵乘法for (i=0;i<n;i+)/n+1 for (j=0;j<n;j+)/n(n+1) cij=0;/n2for (k=0;k<n;k+)/n2(n+1) cij+=aik*bkj;/n3 ,关键操作!执行次数n3和总的程序步2n3+3n2+2n+1有相同的渐近时间复杂度O(n3)。,可以通过考察一个程序中关键操作(key operation)的执行次数,来估算算法的渐近时间复杂度。,关键操作通常是位于算法最内层循环的程序步(或语句),是算法中执行次数最多的操作(程序步) 。,例如:程序1-2 欧几里德迭代算法int Gcd(int m,int n)if (m=0) return n;if (n=0) return m;if (m>n) Swap(m,n);while (m>0) int c=n%m; n=m; m=c;return n;,有时候算法时间的计算并非直截了当,while循环每次迭代后余数值并非按常数因子递减。如何计算迭代次数?,定理2-2 如果n>m ,则n mod m < n/2 。,每次迭代的余数最多是原始值的一半,因此迭代次数为O(logn)。欧几里德算法的时间复杂度为O(logn+logm)。,(2)渐近下界记号 如果存在正常数c和自然数n0,使得当n n0时有f(n) cg(n) ,则称函数f(n)当n充分大时有下界,且g(n)是它的一个下界,记做f(n)=(g(n) 。即f(n)的阶不低于g(n)的阶。,f(n)= O(g(n) g(n)= (f(n),证明(略),(定理2-3) 如果f(n)=amnm+am-1nm-1+a1n+a0是m次多项式,且am>0,则f(n)=(nm)。,(3)紧渐近界记号 如果存在正常数c1,c2和n0,使得当n n0时有c1g(n)f(n) c2g(n),则称函数f(n)与函数g(n)同阶,记做f(n)(g(n)。即f(n)与g(n)的增长阶数相同。,(g(n) = O(g(n) (g(n) 即:f(n) = (g(n) 当且仅当 f(n) = O(g(n) 且 f(n) = (g(n),证明 (略),(定理2-4) 如果f(n)=amnm+am-1nm-1+a1n+a0是m次多项式,且am>0,则f(n)=(nm)。,(4)非紧上界记号o如果对于任何正常数c>0都存在正整数n0 >0,使得当n n0时有f(n)cg(n) (等价于:n时,f(n) / g(n) 0),则称函数f(n)当n充分大时的阶比g(n)低,记做f(n)=o(g(n)。,(5)非紧下界记号 如果对于任何正常数c>0都存在正整数n0 >0,使得当n n0时有f(n)cg(n) (等价于n时,f(n)/g(n)),则称函数f(n)当n充分大时的阶比g(n)高,记做f(n)(g(n)。,

注意事项

本文(算法2_算法分析基础)为本站会员(壹****1)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:https://www.jinchutou.com/h-59.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.