算法2_算法分析基础
72页1、第2章 算法分析基础,学习要点:掌握算法分析中的算法复杂度概念时间复杂度、空间复杂度最好、最坏和平均情况时间复杂度掌握算法分析的渐近表示法掌握用C+语言描述算法的方法章节内容:2.1 算法复杂度2.2 渐近表示法2.3 递推关系(课外阅读),2.1 算法复杂度,好算法的4个重要特征:Correctness正确性,注意区分“正确性”和“健壮性”的概念:算法正确性在合法的输入下,算法应实现预先规定的功能和计算精度要求。程序健壮性当输入不合法的数据时,程序应能做适当处理而不至于引起严重后果。正确性和健壮性互相补充。程序可靠性在正常情况下能正确地工作,在异常情况下也能做出适当处理。,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性,遗憾的是,简单的算法不一定高效,思路清晰、层次分明、容易理解、利于编码和调试。,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性Amount of time/space used效率,执行算法所需的时间和存储空间,算法设计者常常需要在算
2、法的简明性和效率之间作出谨慎的选择,2.1 算法复杂度,好算法的4个重要特征:Correctness正确性Simplicity, clarity简明性Amount of time/space used效率Optimality最优性,算法执行时间达到求解该类问题所需时间的下界。,与所求解问题自身的复杂程度有关。,For problem P, the algorithm A does at most WA(n) steps in the worst case (upper bound)F is a lower bound for a class of algorithm. (lower bound) If WA=F, then A is optimal.,Definition of the optimal algorithm(最优算法),means that: For any algorithm in the class, and any input of size n, there is some input of size n for which the algorithm must
3、perform at least F(n) basic operations.,又如:可证排序问题的时间复杂度下界为(nlogn)。则最坏时间复杂性为O(nlogn)的排序算法是最优算法。因此:堆排序算法和两路合并排序算法都是最优算法。,例如:FindMax(int L) /求n个元素中的最大元素 int max=L0; int i=1; while(in) if (maxLi) max=Li; i=i+1; ,最优算法,影响程序运行时间的因素,程序所依赖的算法问题规模和输入数据计算机系统性能,根本的、起决定作用的,数值大小和状态,硬件系统性能(CPU速度)和软件系统性能(操作系统、编译器),输入、输出,运行一个算法所需的时间和空间资源的量。算法的时间复杂性(Time Complexity)T(n)算法的空间复杂性(Space Complexity)S(n) 其中n是问题的规模(输入大小),算法复杂度,How to Measure? Machine independentLanguage independentProgramming style independentImplement
《算法2_算法分析基础》由会员壹****1分享,可在线阅读,更多相关《算法2_算法分析基础》请在金锄头文库上搜索。
美洲粮食作物的传入对我国农业生产和社会经济的影响
灭菌剂量设定验证方案
六五普法财政局“六五”普法工作总结
含有芴的光电材料
广东省河源市南开实验学校九年级化学上册7.1燃烧和灭火学案无答案新版新人教版
中学生健康调查报告
新人教版七年级数学上册第一章有理数单元测试题
2022广西玉林市兴业生态环境局公开招聘编外人员4人(同步测试)模拟卷(第59版)
深圳纸包装产品项目可行性研究报告
江陵县粮食局安全工作总结 定稿
公立普惠性幼儿园通用幼教教师课程指南中班上学期艺术活动教案多篇汇总版
英语的自我介绍.doc
优秀共产员先进事迹材料
建筑施工员实习心得体会
工程部岗位职责
镇雄县盐化工研发项目投资分析报告【范文参考】
保证合同样本二2
招商引资半年工作总结
标准化工地的建设与管理
乘法的初步认识(教学设计)
2021-12-31 51页
2021-12-30 11页
2021-12-30 12页
2021-12-30 12页
2021-12-30 14页
2021-12-30 12页
2021-12-30 29页
2021-12-30 11页
2021-12-30 16页
2021-12-19 32页