中科院计算机算法分析与设计习题答案.ppt

中科院计算机算法分析与设计习题答案.ppt

  1. 1、本文档共24页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第一章 复杂性分析初步 习题 * 语 句 s/e 频率 总步数 templateclass T void Mult(T **a, T **b, int m, int n, int p) 0 0 0 { for(int i=0; im; i++) 1 m+1 m+1 for(int j=0; jp; j++) { 1 m*(p+1) m*p+m T sum=0; 1 m*p m*p for(int k=0; kn; k++) 1 m*p*(n+1) m*p*n+m*p Sum+=a[i][k]*b[k][j]; 1 m*p*n m*p*n C[i][j]=sum; 1 m*p m*p } } 总 计 2*m*p*n+4*m*p+2*m+1 1. 试确定下述程序的执行步数,该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法: s/e 表示每次执行该语句所要执行的程序步数,频率是指该语句总的执行次数。 2. 函数MinMax用来查找数组a[0:n-1]中的最大元素和最小元素,以下给出两个程序。令n为实例特征。试问:在各个程序中,a中元素之间的比较次数在最坏情况下各是多少? 6. 按照渐进阶从低到高的顺序排列以下表达式: templateclass T bool MinMax(T a[], int n, int Min, int Max) { if(n1) return false; Min=Max=0; //初始化 for(int i=1; in; i++){ if(a[Min]a[i]) Min=i; if(a[Max]a[i]) Max=i; } return true; } 最好,最坏,平均比较次数都是 2*(n-1) templateclass T bool MinMax(T a[], int n, int Min, int Max) { if(n1) return false; Min=Max=0; //初始化 for(int i=1; in; i++){ if(a[Min]a[i]) Min=i; else if(a[Max]a[i]) Max=i; } return true; } 最坏2*(n-1) 最好 n-1, 平均 7. 1)假设某算法在输入规模是 时为 .在某台计算机上实现并完成该算法的时间是 秒. 现有另一台计算机,其运行速度为第一台的64倍, 那么,在这台计算机上用同一算法在 秒内能解决规模为多大的问题? 总时间 原运行速度(时间/每步) 时间复杂度(步数) 规模 关系式: 时间复杂度(计算步数)*运行速度(时间/每步)=运行所需时间 解:设在新机器上 秒内能解决规模为 的问题,时间复杂度为 由于新机器运行速度提高64倍,则运行速度变为 由关系式 ,得 解,得 由于新复杂度 ,新机器的运行速度为 2) 若上述算法改进后,新算法的计算复杂度为 , 则在新机器上用 秒时间能解决输入规模为多大的问题? 代入关系式 ,得 设在新机器上用 秒时间能解决输入规模为 的问题,则 解,得 3)若进一步改进算法,必威体育精装版的算

文档评论(0)

junjun37473 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档