在算法設計與分析里，有這麼兩個算法，減治策略和分治策略。減治我還是第一次聽說，分治之前聽說過，但說實話，減治和分治什麼區別，有時候還真說不上來。今天趁著這個機會，再複習一下這兩個算法分析策略。
減治策略
減治（decrease-and-conquer）技術利用了一個問題給定實例的解和同樣問題較小實例的解之間的某種關係。一旦建立了這種關係，我們既可以從頂向下，也可以從底向上的來運用該關係。
—- 節選自《算法設計與分析基礎》
看不大懂啊，什麼意思？
其實就是說，對於一個問題，減治法的思想在於將原問題拆分為更小規模的子問題，原問題的解和其中一個子問題的解有關聯，不斷縮小規模，然後解決小規模子問題的解，再由子問題與原問題的關係，推出原問題的解。
減治法有3種主要的變化形式：
- 減去一個常量
- 減去一個常量因子
- 減去的規模是可變的
減常量
在減常量變化中，每次算法疊代總是從實例中減去一個相同的常量，一般來說，這個常量等於1，但減去其他常量的情況也偶爾會出現。
舉一個最簡單的例子，計算n!，由其數學公式我們知道， n! = 1 2 3 … n，n!與(n-1)!有關，我們得到其數學公式：
|---- 1 n=0
f(n) = |
|---- f(n-1)*n n>0
求解f(n)，我們把問題規模減至n-1，繼而求解f(n-1)，同理，再減，再減。。。
我們既可以採用自頂向下，遞歸的方式來解決，也可以使用自底向上，疊代的方式來解決問題。
減常量策略一般用的很少，或者說提的不多，一般一個問題涉及到循環遍歷，均可抽象為減常量策略，因為問題的規模確實在常量地減少。
減常量因子
減常量因子在算法的每次疊代中，總是從實例的規模中減去一個常數因子。在大多數應用中，這樣的常數因子等於2。
舉一個減常量因子最出名的例子：二分查找
二分查找也叫折半查找，這裡的常量因子就是2，每次查找時，將問題的規模除以2，因此每次問題的規模都是原來規模的一半。
減可變規模
再比如求兩個整數最大公約數的歐幾里得算法，也是減常量因子策略的一個例子。 gcd(a,b) = gcd(b,a mod b) 。當然這裡的常量因子就不是2了，而是可變的。因為每次疊代減的因子都不同。
其實減治策略思想非常簡單，核心就是將問題的規模不斷縮小，然後減到一個可以很簡單求解的規模，然後解決子問題，再用子問題的解來推原問題的解。一般情況下，這些子問題的解和原問題有著相同或相似的解決思路。
這種問題，在實際代碼上，可以採用遞歸，也可以採用疊代。
分治策略
分治策略很好理解，就是分而治之。
分治策略也是將原問題，拆分為規模更小的問題，然後對每個子問題進行求解，最後合併這些子問題的解得到原問題的解。
這裡和減治策略的區別是，減治策略在拆分子問題後，會捨棄一部分子問題，而分治策略不會捨棄，而是對每個子問題都求解。
歸併排序
分治策略一個常用的例子就是，歸併排序。
將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
如圖所示，先將原無序序列分為左右兩個子序列，對每個子序列遞歸進行歸併排序，然後再將排好序的兩個有序子序列合併，得到原問題的解。
快速排序
在常用的排序算法上，快速排序也是分治策略思想的一個體現。
快速排序是將無序的原序列分為兩部分，其中一部分比另一部分都要小，然後再對這兩部分遞歸使用快速排序，從而達到對原數列排序的目的。
分治策略對並行計算來說是十分理想的，因為各個子問題都可以由各自的CPU同時進行計算。
例題實戰
上面說過了，對於二分查找，使用的是減治思想，大家也很熟悉了。那麼，對於下面這樣一個變種，能否使用分治思想呢？
對於一個對調有序數組，比如[4,5,6,7,8,9,1,2,3]，即把一個有序數組切開，然後前後對調前後部分。如何更高效率的查找元素。
給定一個對調有序數組nums和一個要查找的值target，寫一個方法進行高效率查找。返回target在nums的索引，如果未查找到，返回-1。
這個題目很有意思，是二分查找的一個變種，只不過將二分的有序數組做了下手腳，切開做了個對調。
這個題目可以用減治思想。由於這個對調數組，只切了一下，前後兩部分對調，那麼，當取中間位置時，其左右必然有一個部分是正常的有序區間。
比如上面的[4,5,6,7,8,9,1,2,3]，中間位置8，其左邊是升序區間。
再換一下，比如[7,8,9,1,2,3,4,5,6]，中間位置2，其右邊是升序區間。
我們的思路就是，分兩步減治：
- 先找到升序區間
- 如果元素在升序區間內，直接在升序區間對其進行二分查找
- 如果元素不在升序區間內，那麼我們再對剩下的非升序區間進行步驟1操作。
- 找到元素或區間縮小至只有一個元素時結束查找。
代碼實現：
func binarySearch(nums []int, start, end int, target int) int { if start > end { return -1 } mid := (start + end) / 2 if nums[mid] == target { return mid } if nums[mid] > target { return binarySearch(nums, start, mid-1, target) } if nums[mid] < target { return binarySearch(nums, mid+1, end, target) } return -1}func search(nums []int, start, end int, target int) int { if start >= end { if nums[start] == target { return start } return -1 } mid := (start + end) / 2 // 找出升序區間 ascStart, ascEnd := start, mid nStart, nEnd := mid+1, end if nums[mid] < nums[end] { ascStart = mid ascEnd = end nStart = start nEnd = mid - 1 } // 判斷target是否在升序區間內，如果在，直接二分 if target >= nums[ascStart] && target <= nums[ascEnd] {
return binarySearch(nums, ascStart, ascEnd, target)
}
// 如果不在，則繼續在剩餘非升序區間查找
return search(nums, nStart, nEnd, target)
}
總結
其實，不管是減治策略還是分治策略，其核心都是將問題的規模減小到一定程度，然後去解決小問題，解決完小問題，再根據小問題與原問題的關聯來解決大問題。這也是為啥很多人把二分查找也歸為分治策略的原因，因為其本質差不多的。所以，有時候也沒必要糾結名詞的問題，減治還是分治，都無所謂啦，重要的是，將大規模問題拆解為小規模問題這種思想。