(8.3)-6.3讲稿-算法与程序-算法分析_第1页
(8.3)-6.3讲稿-算法与程序-算法分析_第2页
(8.3)-6.3讲稿-算法与程序-算法分析_第3页
(8.3)-6.3讲稿-算法与程序-算法分析_第4页
(8.3)-6.3讲稿-算法与程序-算法分析_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法与程序计算的效率-算法分析求素数问题：求100到200之间的素数方法一：用这个数除以1到该数之间的每一个整数

如果都不能整除，那么该数为素数例：求101是否为素数就让101除以2到100之间的数，都不能整除，所以101为素数求素数

方案二：我们假设一个数为x,如果该数不是一个素数，那么x一定可以由表达式x=a*b表示，所以当a为2时b可得最大值x/2;当b=2时，a为最大值x/2用x除以2到x/2之间的数即可

求素数如果都不能整除，则说明x为素数求素数还有没有继续优化的空间呢？

方案三：我们发现a和b一定相等或者一大一小，那么我们只需要除以较小的数即可，那么较小的数的范围是多少呢？

求素数x如果为偶数那么x一定不是素数

当a=b时，a=sqrt(x),所以我们只需除以2到sqrt(x)，判断能否被整除求素数怎样去评价和分析一个算法呢？计算机中最重要的两种资源时间空间

设计问题求解的算法时，应该多思考，分析算法，不断寻找更好的解决方案用什么方法来设计算法如何判定一个算法的性能设计的算法需要多少运行时间多少存储空间算法分析是软件开发中必不可少的环节。开发一个软件时

时间效率关注的是算法运行时所需的计算机时间

空间效率则关注算法需要的额外空间

目前算法分析的主要精力集中在分析时间效率上渐进表示法-分析模型任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成为了分析方便，将每种运算所需要的时间统一定义为1个单位算法需要的执行时间为所有运算个数之和

执行时间与问题规模n有关，是n的函数，记作T(n)，T(n)是非负递增函数算法的“渐近时间复杂度”（大O表示法）:输入量n逐渐加大时，时间复杂性的极限情形大O表达式：表示代码执行时间随数据规模增长的变化趋势渐进表示法-分析模型分析模型

这三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数算法的时间复杂度为常数阶，记作T(n)=O(1)

此类算法的时间复杂度是O(1)Temp=i;i=j;j=temp;

分析模型解：第一条语句执行频度为1次，第二条语句执行频度为n次，第三条语句执行频度为n^2，第四条基本语句sum++的执行频度也是n^2计算T(n)=2n^2+n+1=O(n^2)sum=0；

（一次）

for(i=1;i<=n;i++)

（n次）

for(j=1;j<=n;j++)（n^2次）

sum++；

（n^2次）分析模型

a=0;

b=1;

①

for(i=1;i<=n;i++)②

{

s=a+b;③

b=a;④

a=s;⑤

}

解：语句1的频度：2,

语句2的频度：n,

语句3的频度：n-1,

语句4的频度：n-1,

语句5的频度：n-1,

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论