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

"算法分析与设计期末考试复习涵盖了算法的基本特性、时间复杂度分析、算法类型、递归、动态规划、贪心算法、回溯法、最优化问题以及特定问题的解决方案，如Fibonacci数列、三角剖分、哈夫曼编码、最短路径、最小生成树和0/1背包问题。" 1. 算法的基本特性：一个有效的算法应具有输入、输出、有穷性和确定性这四个特性。输入和输出是算法与外部世界的交互，有穷性确保算法能在有限步骤内结束，而确定性意味着给定相同的输入，算法将始终产生相同的结果。 2. 渐进时间复杂度：记号O表示渐进上界，即算法最坏情况下的时间复杂度上限；Ω表示渐进下界，是算法最好情况下的时间复杂度下限。例如，T(n)=3*2^n的时间复杂度为O(2^n)。 3. 计算机性能对算法执行时间的影响：如果一台计算机的速度是另一台的64倍，那么在相同时间内，新计算机可以处理更大规模的问题。例如，原计算机能在t秒内处理规模为n的算法，新计算机则能在t秒内处理规模为n+6的问题。 4. 递归算法的时间复杂度分析：对于递归算法，可以通过递推公式T(N)=2T(N/2)+N/2来求解时间复杂度。根据给出的信息，可以得出时间复杂度为O(NlogN)。 5. 递归算法：直接或间接调用自身的算法称为递归算法，它在解决问题时经常用于处理结构相似的子问题。 6. Fibonacci数列：Fibonacci数列的第n项由前两项之和得出，第4个数是3，第11个数是89。 7. 凸多边形的三角剖分：在有8个顶点的凸多边形中，恰有5条弦和6个三角形。 8. 动态规划与贪心算法：动态规划的关键特征是问题具有最优子结构，即局部最优解能导出全局最优解；贪心算法则是在每一步都做出局部最优决策，期望整体达到最优。 9. 贪心法的应用：贪心法不适用于所有最优化问题，如最大团问题，因为它通常需要全局考虑而非局部最优。 10. 动态规划：动态规划通常采用自底向上的方式求解最优解，通过构建子问题的表格来逐步得到全局最优解。 11. 解决0/1背包问题：贪心法不能保证找到0/1背包问题的全局最优解，而动态规划、回溯法和分支限界法则可以。 12. 贪心算法的应用：哈夫曼编码问题可以用贪心算法解决，因为它可以逐步构建最优解，而LCS问题、批处理作业问题和0-1背包问题则不适合。 13. 回溯法求解装载问题：用回溯法解决最优装载问题时，解空间树的结点个数是所有可能的物品组合，对于m种物品，结点个数为2^m-1。 14. 二分搜索算法：二分搜索是一种基于分治策略的算法，它在有序数组中查找目标值，每次将搜索范围减半。 15. 动态规划的应用：动态规划常用于解决最优化问题，如最长公共子序列、旅行商问题等，但不是所有的最优化问题都能用动态规划解决，如某些问题可能更适合贪心法、回溯法或其他策略。