算法效率的度量和存储空间需求1_第1页
算法效率的度量和存储空间需求1_第2页
算法效率的度量和存储空间需求1_第3页
算法效率的度量和存储空间需求1_第4页
算法效率的度量和存储空间需求1_第5页
全文预览已结束

下载本文档

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

文档简介

1、本课主）算法效率的度量和存储空间需求教学目的:掌握算法的渐近时间复杂度和空间复杂度的意义与作用 教学重点:渐近时间复杂度的意义与作用及计算方法教学难点:渐近时间复杂度的意义 授课内容:一、算法效率的度量算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：1、事后统计的方法。缺点：不利于较大范围内的算法比较。（异地，异时,异境）2、事前分析估算的方法。程序在计算机上运行所需时间的影响因素算法本身选用的策略问题的规模规模越大，消耗时间越多书写程序的语言语言越高级，消耗时间越多编译产生的机器代码质量机

2、器执行指令的速度综上所述，为便于比较算法本身的优劣，应排除其它影 响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的 原操作，以该基本操作重复执行的次数作为算法的时间 量度。(原操作在所有该问题的算法中都相同)7()上示表示率和f(n)的增长率相同，称作算法的渐近时间 复杂度，简称时间复杂度。求4*4矩阵元素和，T(4)=0(f(4)f=n*n;sum(int num4 4) int i, j, r=0;for(i=0;i<4;i+)for(j=0;j<4;j+)r+=numi j ; /*原操作*/return r;)最好情况：T (4) =0 (0)最坏情况：T

3、 (4 ) =0 (n*n)ispass(int num44) int i, j;for(i=0;i<4;i+)for(j=0;j<4;j+)if(numLi Jj!=i*4+j+l)return 0;return 1;原操作执行次数和包含它的语句的频度相同。语句的频 度指的是该语句重复执行的次数。语句频度时间复杂度+x;s=0;10(1)for(i=l;i<=n;+i)+x;s+=x;n0(n)for(j=l;j<=n;+j)for (k=l;k<=n;+k)+x;s+=x;n*n0(n*n)0(log n)基本操作的执行次数不确定时的时间复杂度依基本操作执行次数概率计算平均时间复杂度平均在最坏情况下基本操作执行次最坏情况下时间复杂度数二、算法的存储空间需求类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作：S(n)= 0(f(n)若额外空间相，则称此算法为原地工

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

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

最新文档

评论

0/150

提交评论