Review

1. 2024-10-09 07:27

[!Summary]

一、Introduction #

分治算法（Divide and Conquer）是一种非常重要的算法设计思想，它的核心在于将一个复杂的问题分成两个或多个相同或相似的子问题，直到子问题可以简单地解决为止。然后，再将子问题的解合并起来得到原问题的解。

形象地来说，就是“分而治之”，把一个大问题分成小问题，各个击破，然后再将小问题的解组合起来，得到整个问题的解。

分治算法的一般步骤： #

1. 分解： 将原问题分解为若干个规模较小的子问题，这些子问题是原问题的缩小版。
2. 解决： 若子问题规模足够小，则直接求解；否则，递归地解决这些子问题。
3. 合并： 将子问题的解合并为原问题的解。

分治算法的经典例子： #

• 排序算法： 快速排序、归并排序都是典型的分治算法。
• 查找算法： 二分查找也是一种分治算法。
• 最近点对问题： 将平面上的点集分成两部分，递归地求出每一部分的最近点对，然后考虑跨越分界线的最近点对。
• 大整数乘法： Karatsuba算法将大整数乘法分解为几个较小的整数的乘法和加法。

分治算法的优点： #

• 思路清晰： 分治算法的思想简单易懂，容易实现。
• 效率高： 对于很多问题，分治算法可以显著提高算法的效率。
• 应用广泛： 分治算法在计算机科学的很多领域都有广泛的应用。

分治算法与动态规划的区别： #

推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」

Reference #