《算法设计与分析》第21章.ppt_第1页
《算法设计与分析》第21章.ppt_第2页
《算法设计与分析》第21章.ppt_第3页
《算法设计与分析》第21章.ppt_第4页
《算法设计与分析》第21章.ppt_第5页
免费预览已结束，剩余62页可下载查看

付费下载

下载本文档

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

文档简介

1、第二章算法分析基础，2020年8月3日，成都大学计算机科学系，-2-，2.1算法复杂度2.2渐近表示2.3递归关系，2020年8月3日，成都大学计算机科学系，-3-，主要知识点，掌握算法评价标准；了解影响程序运行时间的因素；掌握算法评估标准：的时间复杂度和空间复杂度的概念；掌握渐近时间复杂度的几种表达式；把握常见时间复杂度的渐近表达式之间的关系。2.1算法复杂度，2020年8月3日，成都大学计算机科学系，-5-，2.1.1什么是好算法？一个好的算法应该具有以下四个重要特征：正确性：算法的执行结果应该满足预先指定的功能和性能要求。简单性：算法应该清晰、组织良好、易于理解，并且有利于编码和调试。效

2、率：算法应有效利用存储空间，具有较高的时间效率。最优性：算法的执行时间已经达到解决这类问题所需时间的下限。2020/8/3，成都大学计算机科学系，-6-，程序健壮性意味着当非法数据被输入时，程序应该能够正确处理它而不会造成严重后果。它的意思是：当一个程序遇到事故时，它能以某种预定的方式做出适当的处理。正确性和健壮性相辅相成。2020年8月3日，成都大学计算机科学系，-7-，2.1.2影响程序运行时间的因素，指程序从开始到结束所需的时间。程序运行所需的时间取决于计算机软件和硬件系统。在同一计算机环境中，影响程序运行时间的主要因素有：程序所依赖的算法；问题规模和输入数据；计算机系统性能。2020年

3、8月3日，成都大学计算机科学系，-8-，算法效率的度量分为预估计和后测试。在后面的测试中，时间函数被插入到算法的某些部分，以确定算法完成某个函数所需的时间。预估计主要分析算法的复杂度，包括空间复杂度和时间复杂度。算法的时间复杂度t(n)；算法的空间复杂度。其中n是问题的大小(输入大小)。预分析的目的是试图得到算法执行特性的形式化描述，并从理论上衡量算法的“好坏”。如何给出反映算法执行特性的描述？最直接的方法：计算算法中各种操作的执行次数，包括：使用了哪些操作，每个操作执行了多少次，以及操作执行一次需要多长时间。算法的执行时间=fi * ti，2020年8月3日，成都大学计算机系，-10-，频率计数示例：x1到n的xx y，y1到n的do x y，j 1到n的do重复x y重复(a) (b) (c)分析：(a): xx y执行一次(b): xx y执行n次(c): xx y执行n2次定义：频率计数：算法中的一个语句或操作。 2020年8月3日，成都大学计算机科学系，-11-，算法插入分类程序插入端口(A(1:n)/按照非降序对A(1:

人人文库> 全部分类> 应用文书 > 项目管理

温馨提示

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

最新文档

评论

0/150

提交评论