1 《算法设计技巧与分析》期末总复习纲要 第一部分 纲要 算法复杂性的渐进阶、估计和比较 三种记号：O , Ω, Θ 意义， 应用 和式的阶的估计，求和的积分近似等 算法复杂性分析的基本方法： 计算迭代次数 计算基本运算的频度 其它 最坏、平均情况下时间复杂性的分析 思考 1. 什么是算法，算法有哪五个特性？ 2. 计算复杂性研究什么内容？包括那两个方面？ 3. 什么是算法的时间复杂性、渐进时间复杂性？ 4. 什么是问题规模、元运算、算法的基本运算及两者的区别？常见的元运算包括哪些？ 5. 在算法复杂性分析中，O 、Ω、Θ 这三个记号的意义是什么？在忽略常数因子的情况下，O 、Ω、Θ 分别提供了算法运行时间的什么界？ 6. 常见的算法复杂性的阶有哪些？它们之间有什么样大 2 小关系？ 7 . 什么是算法的空间复杂性？ 8 . 算法时间复杂性的估计有哪些基本方法？ 9 . 如何运用算法运行的迭代次数、基本运算的频度分析其复杂性？ 1 0 . 算法的最坏情况下时间复杂性和平均情况下时间复杂性的定义是什么？如何估计？ 1 1 . 从算法时间复杂性的角度看，什么样的算法是实际可接受的？ 12. 参见教材、相关课件、作业、实验及思考题：1.13、1.14（b）(c)、1.15(b)、1.23、1.16、1.31 第二部分 纲要 递归方程的分类 分治法相关的特殊方程求解方法 常系数线性非齐次递归方程的递推求解法（或称展开法） 化变系数线性非齐次递归方程为常系数线性非齐次递归方程求解法 思考 1 . 如何用求和的积分近似估计和式的近似值 3 2 . 递推法（展开法）适用于解什么样的递归方程，如何用递推法解递归方程？ 3 . 二价变系数非齐次递归方程的求解。 4 . 用更换变元法求解非齐次递归方程。 5 . 定理2 .5 、2 .6 与分治算法之间的关系，各系数的含义。 6. 参见教材、相关课件、作业、实验及思考题：2.20(c)、(g) 第三部分 纲要 递归算法：递归调用，返回、出口和递归深度或层次 归纳法思想 归纳法步骤：基础步、归纳步及处理过程 算法设计方法与分析： 递归实现归纳思想的算法设计与分析 迭代实现归纳思想的算法设计与分析 其它 迭代与与递归算法互为转换 尾递归 思考 1 . 什么是递归？什么样的算法称为递归算法？ 4 2 . 一个问题满足递归关系是指什么？ 3 . 递归算法设计有些要素？如何应用于递归算法的设计中？ 4 ....
