算法设计技巧与分析.doc

算法设计技巧与分析期末总复习纲要第一部分纲要u 算法复杂性的渐进阶、估计和比较三种记号：O, , 意义， 应用和式的阶的估计，求和的积分近似等u 算法复杂性分析的基本方法： 计算迭代次数 计算基本运算的频度u 其它最坏、平均情况下时间复杂性的分析思考1. 什么是算法，算法有哪五个特性？2. 计算复杂性研究什么内容？包括那两个方面？3. 什么是算法的时间复杂性、渐进时间复杂性？4. 什么是问题规模、元运算、算法的基本运算及两者的区别？常见的元运算包括哪些？5. 在算法复杂性分析中，O、这三个记号的意义是什么？在忽略常数因子的情况下，O、分别提供了算法运行时间的什么界？6. 常见的算法复杂性的阶有哪些？它们之间有什么样大小关系？ 7. 什么是算法的空间复杂性？8. 算法时间复杂性的估计有哪些基本方法？9. 如何运用算法运行的迭代次数、基本运算的频度分析其复杂性？10. 算法的最坏情况下时间复杂性和平均情况下时间复杂性的定义是什么？如何估计？11. 从算法时间复杂性的角度看，什么样的算法是实际可接受的？12. 参见教材、相关课件、作业、实验及思考题：1.13、1.14（b）(c)、1.15(b)、1.23、1.16、1.31第二部分纲要u 递归方程的分类u 分治法相关的特殊方程求解方法 常系数线性非齐次递归方程的递推求解法（或称展开法）化变系数线性非齐次递归方程为常系数线性非齐次递归方程求解法思考1. 如何用求和的积分近似估计和式的近似值2. 递推法（展开法）适用于解什么样的递归方程，如何用递推法解递归方程？3. 二价变系数非齐次递归方程的求解。4. 用更换变元法求解非齐次递归方程。5. 定理2.5、2.6与分治算法之间的关系，各系数的含义。6. 参见教材、相关课件、作业、实验及思考题：2.20(c)、(g) 第三部分纲要u 递归算法：递归调用，返回、出口和递归深度或层次u 归纳法思想u 归纳法步骤：基础步、归纳步及处理过程u 算法设计方法与分析：递归实现归纳思想的算法设计与分析迭代实现归纳思想的算法设计与分析u 其它迭代与与递归算法互为转换尾递归思考1. 什么是递归？什么样的算法称为递归算法？2. 一个问题满足递归关系是指什么？3. 递归算法设计有些要素？如何应用于递归算法的设计中？4. 递归算法适用于解哪些类的问题。5. 归纳法基本思想是什么？6. 如何分析归纳算法的时间复杂性？7. 参见教材、相关课件、作业、实验及思考题：5.3、5.11、5.6、5.28 第四部分纲要u 分治算法设计思想与递归算法之间关系u 分治法四个主要特征u 分治算法设计的步骤u 分治算法与递归方程u 算法设计方法与分析：递归算法实现分治思想的算法设计与分析迭代算法实现分治思想的算法设计与分析u 其它子问题平衡递归实现分治思想、归纳法思想的算法设计与分析迭代实现分治思想、归纳法思想的算法设计与分析思考1. 什么是分治思想？2. 哪些问题类适用于分治思想求解？3. 分治法的最优子结构含义是什么？4. 问题的分解基本原则？5. 分治算法中一定要显式表现划分阶段？6. 治理阶段是终止于子问题能直接求解？7. 对于每个子问题才必须治理求解？8. 分治算法中一定要合并阶段？9. 用递归实现分治思想的算法在时间复杂性方面优于蛮力算法？10. 用迭代实现分治思想的算法是不能用递归方程求解其时间复杂性？11. 在你所学的分治算法中，举例说明它们不同的划分方法是什么？12. 你能说明用分治法实现求Fibonacci序列效率低下的原因是什么？13. 如何分析分治算法的时间复杂性？14. 参见教材、相关课件、作业、实验及思考题：6.6、6.9、6.32、6.37、6.50、6.52、6.44 第五部分纲要u 动态规划的思想u 动态规划的思想特征u 动态规划算法设计的步骤u 动态规划的基本要素u 算法设计方法与分析：自底向上实现动态规划的算法设计与分析(迭代)自顶向下实现动态规划的算法设计与分析(递归)u 其它 最优性原则思考1. 什么是动态规划的思想？2. 哪些问题类适用于动态规划思想求解？3. 动态规划的最优子结构含义是什么？4. 动态规划通常用于解哪一类问题？5. 动态规划求解的问题所具备的基本要素什么？6. 为什么动态规划算法能提高解题的效率？7. 动态规划算法的求解步骤是什么？8. 设计动态规划算法常用的方法是哪两种？各有什么特点和设计要点？9. 动态规划算法中如何避免重复解相同的子问题？求最优值时应保存哪些信息10. 动态规划和分治法都涉及分解子问题，但有何不同？11