第八章 算法设计与分析.pdf

第八章的主题是算法设计与分析，这是计算机科学中的核心概念，涉及到如何有效地解决问题以及评估解决方案的效率。本章涵盖了算法的五个基本特性：有穷性、确定性、可行性、输入和输出。有穷性确保算法在有限步骤内结束，确定性意味着算法执行无歧义，可行性则保证算法可以通过基本运算实现。输入和输出定义了算法处理的数据范围和结果。 算法分析的基础部分主要讨论了时间复杂度和空间复杂度。时间复杂度是衡量算法运行时间随输入规模增长的趋势，通常用大O符号表示。例如，T(n)=3n^3+2n^2+n 的时间复杂度是 O(n^3)。不同的时间复杂度等级表明了算法效率的高低，如 O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)。空间复杂度则是算法在运行过程中临时占用内存的度量，不包括输入和输出数据。 在给定的内部排序算法小结中，涉及到了一个将正实数与负实数分开的算法。该算法的时间复杂度和空间复杂度分别是 O(n) 和 O(n)，因为算法需要遍历整个数组一次，且只使用了常数个额外的存储空间。 递归是算法设计的另一个重要概念，它包括边界条件（终止递归的条件）和递归模式（如何将大问题分解为小问题）。分治法是一种解决问题的策略，将大问题分解为子问题，递归地解决子问题，最后合并子问题的解。常见的分治算法有二分查找、归并排序、快速排序等。 动态规划法是另一种优化问题解决的方法，它通过保存子问题的解来避免重复计算，确保每一步都是最优解，从而达到全局最优。适用场景包括0-1背包问题、矩阵连乘和最长公共子序列。 贪心法则是在每一步选择局部最优解，但不保证整体最优。例如，哈夫曼编码和找零钱问题常常使用贪心策略来快速找到近似最优解。 回溯法是一种系统地搜索所有可能解的方法，适用于解空间树中的问题，如八皇后问题、迷宫问题等。它通过深度优先搜索并回溯来寻找解。 本章涵盖了算法设计的关键概念，包括算法特性、时间复杂度、空间复杂度、递归、分治法、动态规划、贪心法和回溯法，这些都是理解和评估算法效率、设计高效算法的基础。