算法期末复习题final.pdf

【算法分析与设计期末复习知识点】 1. **动态规划法**：动态规划是一种自底向上的求解最优解的方法，通常用于解决具有重叠子问题和最优子结构的问题，如0/1背包问题、最长公共子序列等。动态规划通过构建表格来存储子问题的解，避免了重复计算。 2. **时间复杂度与衡量标准**：衡量一个算法好坏的主要标准是其时间复杂度，即算法执行所需的时间与问题规模的关系。低时间复杂度意味着算法效率高，例如，时间复杂度为O(logn)的算法通常比O(n^2)的算法更优。 3. **分治法**：分治法将大问题分解为两个或更多的相同或相似的子问题，直到子问题可以简单地直接求解，然后将这些子问题的解合并以得到原问题的解。例子包括归并排序、二分搜索等。分治法要求子问题相互独立且与原问题具有相同的结构。 4. **贪心法**：贪心算法在每一步选择局部最优解，期望这些局部最优解能导致全局最优解。它不适用于所有问题，例如皇后问题就不能仅用贪心法解决。最小花费生成树问题和单源最短路径问题可以通过贪心法解决。 5. **回溯法**：回溯法是一种试探性的解决问题的方法，当搜索到某一步发现无法达到目标时，会退回一步尝试其他路径，直到找到解决方案或所有可能路径都尝试过。常用于解决组合优化问题，如八皇后问题。 6. **分支界限法**：采用广度优先策略的搜索算法，如分支界限法，用于在搜索空间中系统地查找问题解，通常用于解决优化问题，避免无效的搜索路径。 7. **算法复杂度分析**：分析算法的计算时间和存储空间需求，是算法设计中的重要部分。例如，快速排序的平均时间复杂度为O(n log n)，最坏情况为O(n^2)。 8. **算法设计策略**：包括分治策略、动态规划、贪心法、回溯法和分支界限法等，是解决不同类型问题的工具。选择合适的设计策略对算法效率至关重要。 9. **编译器影响**：程序执行时间不仅受算法本身影响，还与编译器产生的机器代码质量和计算机执行指令速度有关。 10. **最优子结构**：具有最优子结构的问题意味着局部最优解可以组合成全局最优解，这是动态规划和贪心法的基础。 11. **深度优先搜索（DFS）**：一种按照深度优先遍历状态空间树的算法，常用于回溯法和图的遍历。 12. **分治策略的应用**：合并排序是典型的分治策略应用，将大问题分解为两个或更多小问题，分别排序后合并。 13. **算法执行时间的影响因素**：除了算法设计和问题规模外，还包括硬件性能和编程语言特性等因素。 14. **算法的渐进表示**：如32+10nlogn的渐进表示为O(nlogn)，表示随着n的增长，算法主要由nlogn项决定。 15. **二分搜索**：基于分治法，时间复杂度为O(logn)，适用于有序数据集。 16. **Kruskal算法**：寻找最小生成树的算法，时间复杂度为O(mlogn)，m是边的数量。 17. **回溯法的搜索顺序**：回溯法在状态空间树中按照深度优先遍历顺序搜索。 18. **贪心法设计关键**：关键是选择合适的贪心选择性质，并确保该性质能导致全局最优解。 19. **快速排序**：时间复杂度一般为O(nlogn)，通过随机选择划分基准可以避免最坏情况。 20. **算法的基本性质**：算法必须有明确的输入、输出，指令清晰无歧义，且执行次数有限。 这些知识点涵盖了算法设计与分析的核心概念，包括动态规划、分治法、贪心法、回溯法、分支界限法等，以及它们在不同问题上的应用和时间复杂度分析。