递减与征服

---

想象一下，你正在努力寻找初始问题的解决方案。如果我告诉你，问题的一小部分更容易解决，你可以用这个答案来找到更大的问题的答案呢？有趣吗？递减与征服策略正是这样做的。

“递减与征服”是一种解决问题的策略，它在解决方案过程的每个阶段都减少输入的大小。与分治法类似，它将问题分解成更小的子问题，递减与征服法在每个阶段减少输入数据的大小，而不是增加它。

查找数组中的最大或最小元素，查找一组点中最接近的点对，以及二分查找都是可以使用递减与征服策略解决的一些案例。

由于在每个阶段都会减少输入数据量，从而降低了解决方案的空间和时间复杂度，因此递减与征服的优势在于它经常产生高效的算法。一个糟糕的选择可能会导致一个低效的算法，因此选择最佳的减少输入数据量的方法至关重要。

递减与征服方法的变体

递减与征服策略主要可以采取三种形式

第一种是“递减一个特定值或常数”。

在这个变体中，算法的每次迭代或递归步骤都会将实例的总大小减少相同的常数。虽然可能发生其他常数大小的减少，但这常数通常等于一。许多算法，包括以下算法，都使用这个变体。

拓扑排序、图搜索算法 DFS 和 BFS、插入排序以及生成子集或排列的各种算法就是其中的例子。

第二种是“递减一个常数因子”。

对于算法的每次迭代或递归步骤，此策略都会将问题实例减少一个常数倍。在应用中，这个常数因子通常等于二。除了二之外，以这种因子减少的情况非常罕见。特别是当因子大于 2 时，例如在假币问题中，按常数因子递减的技术特别有效。此策略的应用示例包括

俄罗斯农民乘法、假币问题和二分查找。

第三种或最后一种是“递减可变大小”。

在这个修改中，算法步骤或迭代的大小减少模式会发生变化。虽然计算两个数字的最大公约数问题的第二个参数的值在右边总是小于左边，但它并没有按常数甚至常数因子递减。以下是此策略的一些实际应用示例：

欧几里得算法、插值搜索以及计算中位数和选择问题。

示例 1

一个关于我们如何使用递减与征服方法生成排列的例子

如何用一组 n 个项目（例如 a1、a2、a3……an）获得所有 n! 个排列？为了找到解决方案，生成所有 (n-1)! 个排列。如果解决了这个问题，我们可以通过将 n 放入 (n-1) 个元素的每个排列中的每个位置来解决更广泛的问题。

如果只有一个元素，则只有一个排列，这是递归的基本情况。

示例 2

让我们以二分查找法为例，其中我们应用递减与征服技术。可以使用称为二分查找的搜索方法来查找已排序数组中元素的位置。

使用此方法，始终搜索数组的中间元素。

考虑一个已排序的整数数组，a = {5, 10, 15, 20, 25}。我们想要找到元素 10 的索引。

方法

例如，为了获得 {1,2,3} 的排列

首先，我们找到 {1, 2} 的排列的解决方案

首先找到 {1} 的排列的解决方案，即 {1}

现在我们将 2 插入 {1}，得到：{2 1} 和 {1 2}

将 3 插入 {2 1} 和 {1 2}，得到：{3 2 1} {2 3 1} {2 1 3} {3 1 2} {1 3 2} {1 2 3}

我们生成的排列总数 n! 导致运行时间为 n!。这对于除了最小的 n 值之外的所有值都非常慢，但这并不是算法的错。问题仅仅是生成的对象太少。

为旅行商问题寻找所有路径就是这样一种问题，其中可以应用此方法。

算法

步骤 1：开始

步骤 2：设置 p（要查找位置的元素）

步骤 3：设置指针 first（在第一个位置）和 last（在最后一个位置）

步骤 4：查找中间元素 (mid)

步骤 5：如果 p==mid，则打印中间元素

步骤 6：如果 p>mid，则将 p 与 mid 右边的元素进行比较

步骤 7：如果 p

步骤 8：重复步骤 4 到 7，直到 first 与 last 相遇

步骤 9：返回结果

步骤 10：停止

示例

// Binary Search in C
#include <stdio.h>
int binSearch(int a[], int p, int first, int last) {
   // Repeat till the low and high collide with each other
   while (first <= last) {
   int mid = first + (last - first) / 2;
   if (a[mid] == p)
      return mid;
   if (a[mid] < p)
      first = mid + 1;
   else
      last = mid - 1;
   }
   return -1;
}
int main(void) {
   int a[] = {5, 10, 15, 20, 25};
   int s = sizeof(a) / sizeof(a[0]);
   int p = 10;
   int res = binSearch(a, p, 0, s - 1);
   if (res == -1)
   printf(" Element not present");
   else
  //printing the position of the element
   printf("Element %d is found at index position %d of the array.",p ,res);  
  return 0;
}

输出

执行后，它将产生以下输出

Element 10 is found at index position 1 of the array.

优点

“递减与征服”的一些好处包括：

简单性：与动态规划或分治法等其他策略相比，递减与征服通常更容易实现。

高效算法：由于每个步骤都会减少输入数据的大小，从而降低了结果的时间和空间复杂度，因此该方法经常会产生高效的算法。

针对特定问题：对于可以更快地解决简化版本的问题的特定问题，该方法非常有效。

缺点

递减与征服的一些缺点包括：

针对特定问题：该方法可能不适用于更复杂的问题或所有问题。

实现复杂性：与分治法等其他策略相比，该策略可能更难实现，可能需要更仔细的规划。