算法分析与设计期末复习重点：选择题解析

"《算法分析与设计》期末复习题纲包含选择题，涵盖了算法的基本特性、时间复杂度分析、递归算法、Fibonacci数列、凸多边形的三角剖分、动态规划与贪心算法的应用等多个知识点。" 1. **算法特性**：算法应具备输入、输出、有穷性和确定性这四个基本特性。有穷性意味着算法必须在有限步骤内终止，而确定性是指算法在给定相同输入时应产生相同输出。 2. **时间复杂度**：大O符号（O）表示算法的渐进上界，即算法最坏情况下的时间复杂度；大Ω符号（Ω）则表示渐进下界。在题目中，算法的时间复杂度被用来分析不同计算机上执行效率的差异。 3. **计算能力与输入规模**：更快的计算机可以处理更大规模的问题。如果一台计算机的运行速度是另一台的64倍，那么在相同时间内，它可以解决输入规模增加6位的问题。 4. **递归算法时间复杂度**：对于递归算法的时间复杂度分析，例如T(N)=2T(N/2)+N/2，这种形式通常是线性对数的时间复杂度，即O(NlogN)。 5. **递归算法**：直接或间接调用自身的算法称为递归算法，它在解决问题时会涉及子问题的解决。 6. **Fibonacci数列**：Fibonacci数列的第n个数是前两个数之和。第4个数是3，第11个数是144。 7. **凸多边形的三角剖分**：一个有8个顶点的凸多边形在进行三角剖分时，将形成5条弦和6个三角形。 8. **动态规划与贪心算法**：动态规划和贪心算法的关键区别在于动态规划利用最优子结构，而贪心算法每一步都采取局部最优选择。动态规划通常以自底向上的方式求解问题。 9. **贪心法的应用**：贪心算法适用于具有贪心选择性质的问题，如哈夫曼编码和单源最短路径问题，但不适用于最大团问题，因为它可能需要全局最优解。 10. **动态规划**：动态规划法通常用于自底向上求解最优解，如0/1背包问题、最短路径问题等。 11. **解决0/1背包问题**：贪心法不能解决0/1背包问题，因为局部最优解并不一定能导致全局最优解。动态规划和分支限界法则可以解决这个问题。 12. **贪心算法应用**：哈夫曼编码问题可以用贪心算法求解，因为它满足贪心选择性质。 13. **回溯法求解最优装载问题**：解空间树的节点个数与待选物品的种类数有关，对于m种物品，解空间树的节点个数为2^m - 1。 这些题目涉及的算法和概念是计算机科学基础中的重要组成部分，理解和掌握它们对于理解算法设计与分析至关重要。