分治法介绍

分治法是一种算法模式。在算法方法中，设计是在一个大的输入上接受争议，将输入分解成更小的片段，决定每个小片段上的问题，然后将分段解决方案合并成一个全局解决方案。 这种解决问题的机制称为分治法策略。

分治法算法由以下三个步骤组成。

1. 分解：将原始问题分解为一组子问题。
2. 解决：分别递归地解决每个子问题。
3. 合并：将子问题的解组合起来，得到整个问题的解。

通常，我们可以按照三步过程采用分治法。

示例： 具体的计算机算法基于分治法

1. 最大值和最小值问题
2. 二分搜索
3. 排序（归并排序、快速排序）
4. 汉诺塔。

分治法策略的基本原理

分治法策略有两个基本原理

1. 关系公式
2. 停止条件

1. 关系公式： 它是我们从给定的技术中生成的公式。 在生成公式之后，我们应用分治法策略，即我们递归地分解问题并解决分解的子问题。

2. 停止条件： 当我们使用分治法策略分解问题时，我们需要知道我们需要应用分治法多久。 因此，需要停止分治法递归步骤的条件称为停止条件。

分治法方法应用

以下算法基于分治法的概念

1. 二分查找： 二分查找算法是一种搜索算法，也称为半区间搜索或对数搜索。 它的工作原理是将目标值与排序数组中存在的中间元素进行比较。 在进行比较之后，如果值不同，则无法包含目标的半部分最终将被消除，然后继续搜索另一半。 我们将再次考虑中间元素，并将其与目标值进行比较。 该过程不断重复，直到满足目标值。 如果我们发现搜索结束后另一半为空，则可以得出结论，目标不存在于数组中。
2. 快速排序： 它是最有效的排序算法，也称为分区交换排序。 它首先从数组中选择一个枢轴值，然后将数组的其余元素划分为两个子数组。 通过将每个元素与枢轴值进行比较来进行分区。 它比较元素是否具有大于枢轴值或小于枢轴值，然后递归地对数组进行排序。
3. 归并排序： 它是一种通过进行比较来对数组进行排序的排序算法。 它首先将数组划分为子数组，然后递归地对每个子数组进行排序。 完成排序后，将其合并回原数组。
4. 最近点对： 这是一个计算几何问题。 该算法强调找出度量空间中最近的点对，给定 n 个点，使得点对之间的距离应最小。
5. Strassen 算法： 这是一种矩阵乘法算法，以 Volker Strassen 命名。 事实证明，当处理大型矩阵时，它比传统算法快得多。
6. Cooley-Tukey 快速傅里叶变换 (FFT) 算法： 快速傅里叶变换算法以 J. W. Cooley 和 John Turkey 命名。 它遵循分治法方法，复杂度为 O(nlogn)。
7. Karatsuba 快速乘法算法： 它是传统时间最快的乘法算法之一，由 Anatoly Karatsuba 于 1960 年代后期发明，并于 1962 年出版。 它通过将两个 n 位数减少到最多一位数的方式来相乘。

分治法的优点

• 分治法往往能成功解决最大的问题之一，例如数学难题汉诺塔。 解决您没有基本概念的复杂问题具有挑战性，但借助分治法方法，它可以减少工作量，因为它致力于将主要问题分为两半，然后递归地解决它们。 该算法比其他算法快得多。
• 它可以有效地使用缓存内存，而不会占用太多空间，因为它可以在缓存内存中解决简单的子问题，而不是访问较慢的主内存。
• 它比它的对应蛮力技术更有效。
• 由于这些算法抑制并行性，因此它不涉及任何修改，并且由包含并行处理的系统处理。

分治法的缺点

• 由于它的大多数算法都是通过合并递归来设计的，因此它需要高内存管理。
• 显式堆栈可能会过度使用空间。
• 如果递归执行次数严格大于 CPU 中存在的堆栈，它甚至可能导致系统崩溃。