分治算法

• 用于設計算法的一種常用技巧–分治算法（divide and conquer）。分治算法由兩部分組成：
  • 分(divide)：遞歸然后借機較小的問題（基礎情況除外）
  • 治(conquer)：然后從子問題的解構建原問題的解
• 分治算法一般在主題邏輯中都至少含有兩個遞歸調用的例程，而正文中只有一個遞歸調用的例程不算是分治算法。一般堅持子問題是不想交的（即不重疊）

前幾章中分治算法

• 之前我的文章中，我們依據看到有幾個分支算法，比如
  • 排序算法中的快速排序
  • 二叉樹中的樹的遍歷

案例分析

最大子序列求和問題

• 給定（包含有負數）的整數A1， A2， A3，…AN，求解該集合中子序列的和的最大值${\sum }_{k=i}^j$Ak
• 此問題最簡單的方式暴力雙循環，在這種情況下算法邏輯簡單，但是時間復雜度達到了O(N^2)，如下代碼實現：

/*** @author liaojiamin* @Date:Created in 16:38 2021/1/29*/ public class MaxSumRec {public static int[] getArrayData(int size) {int[] arrayData = new int[size];Random random = new Random();for (int i = 0; i < size; i++) {int temp = random.nextInt(50);if (temp > 25) {arrayData[i] = temp;} else {int value = temp - 2 * temp;arrayData[i] = value;}}return arrayData;}/*** fun1 雙循環 時間復雜度O(N^2)* */public static int getMaxSumRec(int[] arrayData){if(arrayData == null || arrayData.length <= 0){return -1;}if(arrayData.length == 1){return arrayData[0] > 0 ? arrayData[0] : -1;}int max = 0;for (int i = 0; i < arrayData.length; i++) {int sum = 0;for(int j=i; j< arrayData.length; j++){sum +=arrayData[j];if(sum > max){max = sum;}}}return max;}public static void main(String[] args) {int[] arraydata = getArrayData(20);for (int i = 0; i < arraydata.length; i++) {System.out.print(arraydata[i] + ", ");}System.out.println();System.out.println(getMaxSumRec(arraydata));} }

• 但是顯然這不是最優的解法，對應這個存在復雜度為O（NlogN）的解法，我們如下描述。
• 我們采用分治算法（divide-and-conquer）策略。他的思想是將問題分成兩個大致相等的子問題，然后遞歸的對它們求解，這是分的部分，治的部分將兩個子問題的解補充到一起并做少量的附加工作，然后得到整個問題的解法。
• 如上案例中，我們最大子序列可能分布在三個地方：
  • 整個序列在輸入數組的前半部分：可以遞歸求解
  • 整個序列在輸入數組的后半部分：可以遞歸求解
  • 整個序列在輸入數組的中間部分：需要先求出前半部分的最大和（其中包含最后一個元素），在求后半部分最大和（其中包含首個元素），將兩個和相加
• 我給出如下算法實現：

/*** @author liaojiamin* @Date:Created in 16:38 2021/1/29*/ public class MaxSumRec {public static int[] getArrayData(int size) {int[] arrayData = new int[size];Random random = new Random();for (int i = 0; i < size; i++) {int temp = random.nextInt(50);if (temp > 25) {arrayData[i] = temp;} else {int value = temp - 2 * temp;arrayData[i] = value;}}return arrayData;}/*** 分治算法* */public static int getMaxSumRec_1(int[] arrayData){return getMaxSumRecDivide(arrayData, 0, arrayData.length -1);}public static int getMaxSumRecDivide(int[] arrayData, int left, int right){if(left == right){return arrayData[left] > 0 ? arrayData[left] : -1;}int center = (left + right)/2;int maxLeft = getMaxSumRecDivide(arrayData, left, center);int maxRight = getMaxSumRecDivide(arrayData, center + 1, right);int maxLeftBordeSum =0;int leftBordeSum = 0;for(int i = center; i>= left; i--){leftBordeSum+=arrayData[i];if(maxLeftBordeSum < leftBordeSum){maxLeftBordeSum = leftBordeSum;}}int maxRightBordeSum = 0;int rightBordeSum = 0;for(int i = center+1; i<=right;i++){rightBordeSum+=arrayData[i];if(maxRightBordeSum < rightBordeSum){maxRightBordeSum = rightBordeSum;}}return Math.max(Math.max(maxLeft, maxRight), maxLeftBordeSum+maxRightBordeSum);}public static void main(String[] args) {int[] arraydata = getArrayData(20);for (int i = 0; i < arraydata.length; i++) {System.out.print(arraydata[i] + ", ");}System.out.println();System.out.println(getMaxSumRec_1(arraydata));} }

• 如上算法的運行次數分析如下:
  • 令T(N)是求解大小為N的最大子序列的問題所花費的世界。
  • 如果N=1，則只需要執行最基礎情況環肥常數時間量，1個單位時間，得到T(1) = 1；
  • 如果N>1，則必須運行兩個遞歸調用，以及之后的循環，和最后的最大值判斷
  • 因為分治算法保證每個子問題不重疊，那么我們在循環中必然是每個元素范文一次那么我們for循環總共解除到A_0~A_n-1 每一個元素，因此花費O(N)時間，毫無疑問
  • 接著看遞歸部分：我們假設N是偶數，那么兩個遞歸的基數是一樣的，我們每次遞歸得到原來基數數據的一半，那么每一個子遞歸總的花費時間是T(N/2)，（此處可以用數學歸納法證明，N被無限二分達到基數為1 的次數，此處略）
  • 因此遞歸共花費2T(N/2)個時間單位，
  • 如上總數花費時間：2T(N/2) + O(N)

T(1) = 1 T(N) = 2T(N/2) +O(N)

• 得到如上的數學公式，為簡化計算，我們用N代替O(N)項，由于T(N)最終還是要用大O表示，因此這么做不影響答案
• 此處我們只進行遞推，不進行數學證明，依據以上公式，T(N) = 2T(N/2)+N，且T(1) = 1
• 那么我們得到 T(2) = 2T(1) + 2 = 4 = 22， T(4) = 2T(2) + 4 = 12 = 43 … T(16) = 2T(8) + 16 = 80 = 16*5
• 若N=2^k,則 T(N) =N*(k+1) = N*LogN +N = O(NlogN)

最大子序列和投機方法

• 一個循環解決此問題，如下實現：

public static int getMaxSumRec_2(int[] arrayData){int maxSum = 0, thisSum = 0;for (int i = 0; i < arrayData.length; i++) {thisSum+=arrayData[i];if(thisSum > maxSum){maxSum = thisSum;}else if (thisSum < 0){//如果之前項累計不大于0， 則情況之前項和，從小計數thisSum = 0;}}return maxSum;}

再談快排

• 快速排序是經典的分支算法應用，我們在之前的排序歸納文章中已經給出過具體的算法分析以及實現，基本算法都是如下幾個步驟：
  • 如果S集合中元素個數是0或者1，則返回
  • 取S中任何一個元素V，稱為樞紐元（pivot）
  • 將S-{V}（S中其他元素）劃分為兩個不想交的集合：S1 = { X \in S-{V} |X<=V | } 和 S2 = { X \in S-{V} |X>=V | }
  • 返回{quickSort(S1)} 后跟v，繼續返回 quickSort(S2)
• 以上算法中針對樞紐元的選擇上并沒有詳細處理，因此這就成了一種設計決策，一部分好的實現方法是將這種情形盡可能完美的解決。直觀的看，我們洗碗能將集合中的一半關鍵字分配到S1 中，另外一半分配到S2，很想二叉樹。

樞紐元選擇

• 雖然不管樞紐元選擇的那個元素，最終都能完成排序，但是有些選擇明顯更優秀。
• 錯誤的選擇方式：
  • 我們之前的算法中直接選擇的第一個元素作為樞紐元，因為當時的算法說明中數據來源是隨機生成數組成的數列，那么這種情況是可以接受的。當時如果輸入的數列是已有序的數列，或者反序列，那么這樣的樞紐元選取會產生一個最差情況的分割，因為所有的元素不是被分配到S1就是S2，并且這種情況會發生在遞歸排序的所有調用中。時間復雜度O(N^2)
  • 另外一種方法是選取前兩個互異的關鍵字中的較大者作為樞紐元，不過這種值選取第一個元素作為樞紐元具有相同的問題，
• 一種安全的做法：
  • 隨機選擇樞紐元，一般來說這種策略非常安全，除非隨機數發生器有問題，因為隨機的樞紐元不可能總在接連不斷的產生劣質的分割，另一方面，隨機數的生成開銷比較大，根本減少不了算法其余部分的平均運行時間。
  • 三數中值分割法（Median-of-Three Partitioning） :一組N個數的中值是滴N/2 個最大的數。樞紐元最好的選擇數是數組的中值。但是，這很難算出并且明顯減慢快排的速度，這樣的中值的估計量我們可以通過隨機選取三個數并用他們的中值作為樞紐元而得到。而實際上，隨機性并沒有這么大的幫助，因此一般的做法是使用左端，右端和中間位置的三個元素的中值作為樞紐元。

分割策略

• 有幾種分割策略用于實踐，我們給出的分割策略已經被證明能夠給出好的結果。我們將樞紐元與最后的元素交換，使得樞紐元離開要被分割的數據段。i從第一個數據開始，j從倒數第二個元素開始。我們用如下動圖
  
• 上圖用的交換法，當i在j左邊的時候，我們將i右移，移過哪些小于樞紐元的元素，并且建j左移，移過哪些大于樞紐元的元素，當i和j停止時候，i指向一個大元素，j指向一個小元素。如果i在j左邊，那么將交換這兩個元素。最后效果是將大元素推向右邊，小元素推向左邊。最后如果i 到了j 的右邊，并且停在第一個最大的元素時候，我們停止交換i， j ，并且將pivot與i 交換。
• 在最后一個步驟當樞紐元與i 所指向的元素交換的時候，我們知道，在位置position < i 的每一個元素都必須小于樞紐元，類似position > i 的元素都大于樞紐元。
• 必須考慮的一個重要情況，如何處理等于樞紐元情況，i ，j 應該做相同的動作，否則分割將會偏向一方。
• 極端情況，所有數據相等，那么我們每次都需要交換，雖然沒有意義，但是i ，j， 將會在中間交錯，時間復雜度O(NlogN)
• 實際情況，幾乎不會存在都相同情況，所以我們讓i， j，都停止，并交換。

小數組

• 對于很小的數組（N <= 20）,快速排序不如插入排序快

快速排序實現

/*** @author liaojiamin* @Date:Created in 12:06 2021/2/1*/ public class DivideAndConquerGreat {public static void main(String[] args) {int[] beginArrayData = getArrayData(30);System.out.println("------------------");int[] arrayData = quickSort(beginArrayData);for (int i = 0; i < arrayData.length; i++) {System.out.println(arrayData[i]);}}public static int[] quickSort(int[] arrayData) {if (arrayData == null || arrayData.length <= 1) {return arrayData;}return quickSort(arrayData, 0, arrayData.length - 1);}public static int[] quickSort(int[] arrayData, int left, int right) {if(Math.abs(left - right) <= 20){insertionSort(arrayData, left, right);}else {if (left < right) {int position = swap(arrayData, left, right);quickSort(arrayData, left, position - 1);quickSort(arrayData, position + 1, right);}}return arrayData;}/*** 快排主體實現*/public static int swap(int[] arrayData, int left, int right) {int position = median3(arrayData, left, right);int i = left ;int j = right - 1;while (i < j) {while (i < j && arrayData[i] <= position) {i++;}while (i < j && arrayData[j] >= position) {j--;}if (i < j) {swapElement(arrayData, i, j);}}//position初始位置是right-1swapElement(arrayData, i, right - 1);return i;}/*** 數據交換*/public static void swapElement(int[] arrayData, int i, int j) {int temp = arrayData[i];arrayData[i] = arrayData[j];arrayData[j] = temp;}/*** 三數中值獲取*/public static int median3(int[] arrayData, int left, int right) {int center = (left + right) / 2;if (arrayData[center] < arrayData[left]) {swapElement(arrayData, center, left);}if (arrayData[right] < arrayData[left]) {swapElement(arrayData, right, left);}if (arrayData[right] < arrayData[center]) {swapElement(arrayData, right, center);}swapElement(arrayData, center, right - 1);return arrayData[right - 1];}/*** 插入排序*/public static int[] insertionSort(int[] arraydata, int left, int right) {if (arraydata == null || arraydata.length <= 1) {return arraydata;}for (int i = 0; i <= right; i++) {for (int j = i; j > left; j--) {if (arraydata[j - 1] > arraydata[j]) {int temp = arraydata[j - 1];arraydata[j - 1] = arraydata[j];arraydata[j] = temp;}}}return arraydata;}/*** 隨機生成數列*/public static int[] getArrayData(int size) {int[] arrayData = new int[size];Random random = new Random();for (int i = 0; i < size; i++) {int temp = random.nextInt(10);if (temp > 0) {arrayData[i] = temp;} else {int value = temp - 2 * temp;arrayData[i] = value;}System.out.println(arrayData[i]);}return arrayData;} }

上一篇：數據結構與算法–貪婪算法2

總結

以上是生活随笔為你收集整理的数据结构与算法--分治算法-最大子序列和问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。