在算法設計與分析裡，有這麼兩個算法，減治策略和分治策略。減治我還是第一次聽說，分治之前聽說過，但說實話，減治和分治什麼區别，有時候還真說不上來。今天趁着這個機會，再複習一下這兩個算法分析策略。

減治策略

減治（decrease-and-conquer）技術利用了一個問題給定實例的解和同樣問題較小實例的解之間的某種關系。一旦建立了這種關系，我們既可以從頂向下，也可以從底向上的來運用該關系。

—- 節選自《算法設計與分析基礎》

看不大懂啊，什麼意思？

其實就是說，對于一個問題，減治法的思想在于将原問題拆分為更小規模的子問題，原問題的解和其中一個子問題的解有關聯，不斷縮小規模，然後解決小規模子問題的解，再由子問題與原問題的關系，推出原問題的解。

減治法有3種主要的變化形式：

1. 減去一個常量
2. 減去一個常量因子
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. 先找到升序區間
2. 如果元素在升序區間内，直接在升序區間對其進行二分查找
3. 如果元素不在升序區間内，那麼我們再對剩下的非升序區間進行步驟1操作。
4. 找到元素或區間縮小至隻有一個元素時結束查找。

代碼實現：

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) }

總結

其實，不管是減治策略還是分治策略，其核心都是将問題的規模減小到一定程度，然後去解決小問題，解決完小問題，再根據小問題與原問題的關聯來解決大問題。這也是為啥很多人把二分查找也歸為分治策略的原因，因為其本質差不多的。所以，有時候也沒必要糾結名詞的問題，減治還是分治，都無所謂啦，重要的是，将大規模問題拆解為小規模問題這種思想。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!