《算法技術手冊》一3.6.2 分治

分治通常是将一個規模為n的問題劃分成兩個獨立的子問題，其中每個子問題的規模約為n/2。大部分時候分治政策是遞歸形式的，并且會有簡單易懂的基本條件用于結束遞歸。此外，在計算出兩個較小問題的解之後，還必須要有一些計算來根據子問題的解計算出原問題的解。

下面來看一個例子：求包含n個數的數組中的最大元素。例3-2展示了如何将原問題分解成兩個子問題并通過遞歸求解。通常，最大值一般是兩個子集各自的最大值中比較大的那一個。仔細觀察尾遞歸觸發的條件，即子集中隻有一個元素vals[left]傳回。

例3-2：遞歸分治求數組中最大值

/* 開始使用遞歸函數 /

public static int maxElement(int[] vals) {

if (vals.length == 0) {

}

return maxElement(vals, 0, vals.length);

/** 計算vals[left, right)的最大元素

注意vals[right]并不在計算之列 */

int maxElement(int[] vals, int left, int right) {

if (right - left == 1) {

// 計算子問題

int mid = (left + right) / 2;

int max1 = maxElement(vals, left, mid);

int max2 = maxElement(vals, mid, right);

// 合并處理:從子問題的解中得到目前問題的解

if (max1 > max2) { return max1; }

return max2;

例3-2中分治算法的時間複雜度是O(n)，因為子問題解的合并處理在常數時間内就能完成。如果這一步需要O(n)時間，那麼整體的時間複雜度将會上升至O(n log n)。當然，我們也可以不用分治算法，直接周遊數組并且記下目前所找到的最大值。是以，就當是一個小小的提示吧：分治算法并不總是最快的。