算法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_算法分析基础》请在金锄头文库上搜索。
酒店员工个人总结(6篇)
管理员辞职报告
英语完形填空(精品)
西工大画法几何及建筑制图下B卷18年10月作业考核答案解析
东北大学21春《计算机辅助设计》在线作业一满分答案72
护士读书笔记15篇
宣传保护树木人人有责的标语
电子商务平台及工作量评估分析
防偷防盗宣传标语3条_ (2)
初二第一学期学习总结
2022年文员实习日记3篇(精选模板)
最新北师大版数学必修二课时作业:2.2.1圆的标准方程含答案
社会交往中的六大著名法则(2)
幼儿小班环保备课教案
点心、烧腊主管、洗菜工工作职责范本
酒店客人投诉案例分析及处理方案
2022年华润内蒙古医药有限公司“采购专员”岗位招聘考试历年高频考点试题含答案解析
六年级故事作文300字
餐饮工作人员年底工作总结1000字
注射用硫酸头孢匹罗
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页