算法与分析总结范文.doc_第1页
算法与分析总结范文.doc_第2页
算法与分析总结范文.doc_第3页
全文预览已结束

下载本文档

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

文档简介

算法与分析总结范文 1:如果题目改为求1351000算法只需作很少的改动S1p=1S2i=3S3p=pi S4i=i+2S5若i1000，返回S3。 否则，结束。 Lianchen(n)p1i3while i=n dopp*i i=i+2return p2.冒泡排序（bubble sort） （2）伪代码描述算法BUBBLE-SORT(A)1for i1to lengthA2do forjlenthAdownto i+13do ifAj （3）用程序如何描述冒泡排序算法？void bubblesort(int A,int n)int i,j,temp;for(i=0;ii;j-)if(Aj （1）多项式时间算法（polynomial timealgorithm)用多项式来对计算时间限界的算法。 O (1) （2）指数时间算法（exponential timealgorithm)计算时间用指数函数限界的算法。 O(2n) 2.递归地定义最优值。 3.以自底向上的方式计算出最优值。 4.根据计算最优值时得到的信息，构造最优解。 （2）考察一个0-1背包问题的实例如下n=5，W=10，w=2,2,6,5,4，v=6,3,5,4,6【例3】矩阵链乘问题【计算举例】已知矩阵大小如表，计算A1*A2*A3*A4*A5所需的最小乘法次数和对应的计算次序（即加括号方式）。 m计算最优值已知P0=3;P1=5;P2=7;P3=4;P4=6;P5=8?jipppjkmkimjijijki,1,minki0,1j计算最优值算法复杂度分析算法matrixChain的主要计算量取决于算法中对l，i和k的3重循环。 循环体内的计算量为O (1)，而3重循环的总次数为O(n3)。 因此算法的计算时间上界为O(n3)。 算法所占用的空间显然为O(n2)。 例如3.7最长公共子序列（LCS）【例4】第5章回溯法回溯法的基本做法是搜索，是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，回溯法的基本步骤 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。 5.40-1背包问题【例】n=3,W=30,w=16,15,15,v=45,25,25例题的状态空间树5.3子集和数问题(subset-sum problem)【例】n=5，(p1,p2,p3,p4,p5)=(5,10,12,13,15),S
人人文库> 全部分类> 应用文书 > 年终总结

温馨提示

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

最新文档

评论

0/150

提交评论