演算法思想——分治演算法

• 2019 年 10 月 3 日
• 筆記

一、分治策略

　　“分而治之”，大問題能夠拆成相似的小問題，記住這些小問題需要具有相似性。而後將小問題的每個解合成為大問題的解。所以說大問題如何拆，小問題如何合併才是這個演算法最主要的一個思想。實際上很多演算法如貪心演算法，動態規劃等等都是要求把大問題拆成小問題。而分治演算法的重要一點就是要適用於能夠重新把小問題的解合併為大問題的解。

二、分治法適用條件

　　1、該問題的規模縮小到一定程度就可以很容易解決；

　　2、該問題可以分解為若干個規模較小的相同問題，這裡注意是最優子結構性質；

　　3、利用該問題分解出的子問題的解可以合併為該問題的解；

　　4、該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共子問題；

　　對於很多演算法而言，第一條往往是必要的，因為數據量一旦大起來，問題往往複雜度上升的特別快。這裡就需要將這個大問題分解為小問題。小問題處理起來更加方便。第二、三條的才是分治思想的核心，因為很多時候我們會採用遞歸的方式進行解決，所以在大問題分解為小問題的時候需要保證小問題之間的相同性。單單分解為小問題之後還不能算完成，必須要能夠將小問題的解合併為這個問題的最終解才能算真正用到了分治的思想。最後一條也是最關鍵的，各個子問題之間必須要保證獨立性，即不互相影響。如果相互之間有影響，這時候我們採用的是動態規劃就更加好一點。

三、例題

　　其實演算法的思想不用講太多，能夠化為幾句話是最好的，下面就舉幾個例子來看看分治演算法：

　　例題一：二分查找，給定一個按照升序排好的數組array，要在這個數組中找出一個特定的元素x；

　　當我們遇到一個問題，完全可以在心裡問自己下面四個問題：

　　1、當前問題能不能切分？

　　答：能切分，因為數組按照升序來排列。所以當x大於某個元素array[mid]時，x一定在array[mid]的右邊。以此再來切分。每次切一半

　　2、分解出來的子問題相同嗎？

　　答：相同，每個子問題的數據集都是父問題的1/2倍。並且每次只比較子問題的中間的數據

　　3、子問題的解能合併為父問題的解嗎？

　　答：不需要合併，子問題的解即為父問題的解。

　　4、子問題之間相互獨立嗎？

　　答：獨立，子問題只是判斷，不需要和父問題有很強的關聯性（這裡可以參考一下動態規劃演算法，就能理解子問題之間怎麼判斷是獨立的）

public class Main{    public int BinarySearch(int[] array,int x,int left,int right){            while(left<=right){              int mid=(left+right)/2;              if(array[mid]==x){                  return mid;              }              if(array[mid]>x)right=mid-1;              else left=mid+1;          }          return -1;      }  }

　　例題二：歸併排序，給定一個無序數組array[7]={49,38,65,97,76,13,27}，使其變的有序

　　同樣在自己心裡問問4個問題

　　1、當前問題能切分嗎？

　　答：能，最簡單的就是兩個數之間的比較，這個數組可以看成多個兩個數來比較

　　2、分解出來的子問題是否相同？

　　答：相同，都是兩個數比較大小。

　　3、子問題的解能夠合成父問題的解嗎？

 　　答：每兩個有序數組再按照一定順序合起來就是最終的題解。這裡就是有個合併的過程

　　4、子問題之間相互獨立嗎？

　　答：獨立，分到最小的時候子問題之間互不影響。

　　下面是歸併排序程式碼：

public class MergeSort {        public static void merge(int[] arr,int l,int mid,int r){          int[] aux= Arrays.copyOfRange(arr,l,r+1);          int i=l,j=mid+1;          for(int k=l;k<r;k++){              if(i>mid){                  arr[k]=aux[j-l];                  j++;              }              else if(j>r){                  arr[k]=aux[i-l];                  i++;              }              else if(aux[i-l]<aux[j-l]){                  arr[k]=aux[i-l];i++;              }              else {                  arr[k]=aux[j-l];j++;              }          }        }      // 遞歸使用歸併排序,對arr[l...r]的範圍進行排序      public static void sort(int[] arr, int l, int r) {            if (l >= r)              return;            int mid = (l+r)/2;          sort(arr, l, mid);          sort(arr, mid + 1, r);          merge(arr, l, mid, r);      }  }

　　歸併的示意圖如下：

　　最後問題來了，快速排序是用了分治演算法的思想嗎？

四、總結

　　分治演算法只是一種思想，不是一個具體的套路，只能說在碰見具體問題時我們能夠從這個思路去思考，切分問題？合併問題？子問題之間影響關聯大不大？這些都是具體問題具體考慮。還有很多很多題目是用了分治演算法。也可以多刷刷題