华农信息学院冯在文教授讲解分治法：二分搜索与合并排序

第六讲（分治法二）主要探讨了分治算法这一核心概念及其在计算机科学中的广泛应用。分治法是一种解决问题的策略，它将复杂问题分解成规模较小且相互独立的子问题，通过递归地解决这些子问题，最终合并子问题的解来求得原问题的解。本章内容分为以下几个部分： 1. 分治基本概念：介绍了分治算法的基本形式，即问题被划分为相似的子问题，递归地解决这些子问题，然后将子问题的解合并成原问题的解答。这种算法通常遵循三个步骤：划分、治理和组合。 2. 两个简单例子：通过二分搜索和合并排序作为分治法的经典应用示例。二分搜索利用分治策略在有序数组中查找特定元素，而合并排序则是将数组分成两半，分别排序后合并，直至整个序列有序。 3. 分治范式：详细阐述了分治算法的一般步骤，包括： - 划分：将输入数据分割成p（通常为2）个相等或接近相等的部分。 - 治理：对于规模大于阈值的问题，递归调用算法解决子问题。 - 组合：将子问题的解合并，形成最终结果。 4. 选择算法：涉及如何根据问题特性和规模选择合适的分治算法，如快速排序，这是一种高效的选择排序方法，通过分治实现快速排序数组。 5. 大整数乘法和矩阵乘法：展示了分治法在处理数值计算中的应用，如将大整数分解为较小部分进行逐位相乘，以及矩阵分解为行或列的子矩阵进行乘法。 6. 最近点问题：这是一个典型的几何问题，通过分治策略可以有效地找到两个点集之间的最近点对。 7. 寻找最大值和最小值：通过MINMAX算法实例，展示了如何使用分治法在一个数组中同时找到最大值和最小值，降低了比较次数。 8. 问题描述与算法设计：针对实际问题，提出了优化算法的设计思路，比如通过分治将问题简化，减少不必要的计算。 总结来说，第六讲深入浅出地讲解了分治法的核心原理和实际应用，涉及了多种常见的算法和问题解决策略，有助于理解和掌握这一重要的算法设计思想。