第一章算法与程序设计简介.pptVIP

  1. 1、本文档共31页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第一章算法与程序设计简介

Visual FoxPro 2. 算法描述举例 【例1.1】 求两个整数a,b(ab)的最大公约数的欧几里德算法: (1) a除以b得余数r;若r=0,则b为所求的最大公约数。 (2) 若r≠0,以b为a,r为b,继续(1)。 注意到任两整数总存在最大公约数,上述辗转相除过程中余数逐步变小,相除过程总会结束。 欧几里德算法又称为“辗转相除”法,具体描述如下: 输入正整数a,b; if(ab) {c=a;a=b;b=c;} /* 交换a,b ,确保ab */ r=a%b; while(r!=0) { a=b;b=r; /* 实施辗转相除 */ r=a%b; } printf(最大公约数b); 算法复杂性的高低体现运行该算法所需计算机资源的多少。 算法的复杂性越高,所需的计算机资源越多;反之,算法的复杂性越低,所需的计算机资源越少。 计算机资源,最重要的是时间资源与空间资源。 需要计算机时间资源的量称为时间复杂度,需要计算机空间资源的量称为空间复杂度。 算法分析是指对算法的执行时间与所需空间的估算,定量给出运行算法所需的时间数量级与空间数量级。 在分析算法时,隐藏细节的数学表示法成为大写O记法 一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句(运算)的多少。算法的时间复杂度通常用该算法执行的总的语句(运算)的数量级决定。 就算法分析而言,一条语句的数量级即执行它的频数,一个算法的数量级是指它所有语句执行频数之和。 1. 时间复杂度定义 定义: 对于一个数量级为的 算法,如果存在两个正常数c和m,对所有的n≥m,有 则记作 ,称该算法具有 用 的运行时间,是指当n足够大时,该算法的实际运行时间不会超过的某个常数倍时间。 2. 例如程序段: for(k=1;k=n;k++) { x=x+y; y=x+y; s=x+y; } 每个赋值语句执行频数为n,该算法的数量级为3n; 其计算时间即时间复杂度为O(n)。 3. 例如程序段: for(t=1,k=1;k=n;k++) {t=t*2; for(j=1;j=t;j++) s=s+j; } 内循环赋值语句执行频数 算法的时间复杂度为O( )。 4. 算法时间关系: 常见多项式时间算法: 常见指数时间算法: 一般地,当n取值比较大时,在计算机上实现指数时间算法是不可能的,就是比时间复杂度 高的多项式时间算法运行也很困难。 5. 两个定理 定理1.1 时间复杂度符号O有以下运算规则: O(f)+O(g)=O(max(f,g)) (1.1) O(f)O(g)=O(fg) (1.2) 定理1.2 如果 是n的m次多项式,则 (1.3) 【例1.3】 估算下列程序段代表算法的时间复杂度。 (1) t=1;m=0; for(k=1;k=n;k++) { t=t*2; for(j=t;j=n;j++) m++; } 时间复杂度为O(nlogn). (2) m=0; for(k=1;k=n;k++) for(j=k*k;j=n;j++) m++; 时间复杂度为O( ). 注意(1)、(2)中m++语句的执行次数 的计算,具体见教材详列。 一个算法的运行时间,与问题的规模相关,也与输入的数据相关。 对算法的改进与优化,主要表现在有效缩减算法的运行时间与所占空间。 例如把求解某一问题的算法时间从 优化缩减为 就是一个了不起的成果。 或者把求解某一问题的算法时间的系数缩小,例如从2n缩小为3n/2,尽管其时间数量级都是,系数缩小了也是一个算法改进的成果。 算法的空间复杂度是指算法运行的存储空间,是实现算法所需的内存空间的大小。 一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。 固定空间需求包括程序代码、常量与结构变量等所占的空间。 可变空间需求包括数组元素所占的空间

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档