遞減與征服

---

想象一下，你正在努力尋找初始問題的解決方案。如果我告訴你，問題的一小部分更容易解決，你可以用這個答案來找到更大的問題的答案呢？有趣嗎？遞減與征服策略正是這樣做的。

“遞減與征服”是一種解決問題的策略，它在解決方案過程的每個階段都減少輸入的大小。與分治法類似，它將問題分解成更小的子問題，遞減與征服法在每個階段減少輸入資料的大小，而不是增加它。

查詢陣列中的最大或最小元素，查詢一組點中最接近的點對，以及二分查詢都是可以使用遞減與征服策略解決的一些案例。

由於在每個階段都會減少輸入資料量，從而降低了解決方案的空間和時間複雜度，因此遞減與征服的優勢在於它經常產生高效的演算法。一個糟糕的選擇可能會導致一個低效的演算法，因此選擇最佳的減少輸入資料量的方法至關重要。

遞減與征服方法的變體

遞減與征服策略主要可以採取三種形式

第一種是“遞減一個特定值或常數”。

在這個變體中，演算法的每次迭代或遞迴步驟都會將例項的總大小減少相同的常數。雖然可能發生其他常數大小的減少，但這常數通常等於一。許多演算法，包括以下演算法，都使用這個變體。

拓撲排序、圖搜尋演算法 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.

優點

“遞減與征服”的一些好處包括：

簡單性：與動態規劃或分治法等其他策略相比，遞減與征服通常更容易實現。

高效演算法：由於每個步驟都會減少輸入資料的大小，從而降低了結果的時間和空間複雜度，因此該方法經常會產生高效的演算法。

針對特定問題：對於可以更快地解決簡化版本的問題的特定問題，該方法非常有效。

缺點

遞減與征服的一些缺點包括：

針對特定問題：該方法可能不適用於更復雜的問題或所有問題。

實現複雜性：與分治法等其他策略相比，該策略可能更難實現，可能需要更仔細的規劃。