2022年算法设计技巧与分 .pdf
《2022年算法设计技巧与分 .pdf》由会员分享,可在线阅读,更多相关《2022年算法设计技巧与分 .pdf(7页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1 算法设计技巧与分析期末总复习纲要第一部分纲要算法复杂性的渐进阶、估计和比较三种记号: O, , 意义,应用和式的阶的估计,求和的积分近似等算法复杂性分析的基本方法:计算迭代次数计算基本运算的频度其它最坏、平均情况下时间复杂性的分析思考1. 什么是算法,算法有哪五个特性?2. 计算复杂性研究什么内容?包括那两个方面?3. 什么是算法的时间复杂性、渐进时间复杂性?4. 什么是问题规模、 元运算、 算法的基本运算及两者的区别?常见的元运算包括哪些?5. 在算法复杂性分析中,O、 这三个记号的意义是什么?在忽略常数因子的情况下,O、 分别提供了算法运行时间的什么界?6. 常见的算法复杂性的阶有哪些
2、?它们之间有什么样大名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 7 页 - - - - - - - - - 2 小关系?7. 什么是算法的空间复杂性?8. 算法时间复杂性的估计有哪些基本方法?9. 如何运用算法运行的迭代次数、基本运算的频度分析其复杂性?10. 算法的最坏情况下时间复杂性和平均情况下时间复杂性的定义是什么?如何估计?11. 从算法时间复杂性的角度看,什么样的算法是实际可接受的?12. 参见教材、相关课件、作业、实验及思考题:1.13、1.14(b)(c
3、)、1.15(b)、1.23、1.16、1.31 第二部分纲要递归方程的分类分治法相关的特殊方程求解方法常系数线性非齐次递归方程的递推求解法(或称展开法)化变系数线性非齐次递归方程为常系数线性非齐次递归方程求解法思考1. 如何用求和的积分近似估计和式的近似值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 7 页 - - - - - - - - - 3 2. 递推法 (展开法) 适用于解什么样的递归方程,如何用递推法解递归方程?3.二价变系数非齐次递归方程的求解。4.用更换
4、变元法求解非齐次递归方程。5.定理 2.5、2.6 与分治算法之间的关系,各系数的含义。6. 参见教材、相关课件、作业、实验及思考题:2.20(c)、(g) 第三部分纲要递归算法: 递归调用, 返回、出口和递归深度或层次归纳法思想归纳法步骤: 基础步、归纳步及处理过程算法设计方法与分析:递归实现归纳思想的算法设计与分析迭代实现归纳思想的算法设计与分析其它迭代与与递归算法互为转换尾递归思考1. 什么是递归?什么样的算法称为递归算法?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年算法设计技巧与分 2022 算法 设计 技巧
限制150内