分治算法是用了分治思想的一種算法，什麼是分治？

字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

舉個栗子：

分治模式中，我們遞歸地求解一個問題，在每層遞歸中應用如下三個步驟：

• 分解（Divide)步驟将問題劃分為一些子問題，子問題的形式與原問題一樣，隻是規模更小。
• 解決(Conquer)步驟遞歸地求解出子問題。如果子問題規模足夠小，則停止遞歸，直接求解。
• 合并（Combine）步驟将子問題的解合并為原問題的解。

運用分治策略解決的問題一般來說具有以下特點：

• 原問題可以分解為多個子問題

這些子問題與原問題相比，隻是問題的規模有所降低，其結構和求解方法與原問題相同或相似。

• 原問題在分解過程中，遞歸地求解子問題

由于遞歸都必須有一個終止條件，因此，當分解後的子問題規模足夠小時，應能夠直接求解。

• 在求解并得到各個子問題的解後

應能夠采用某種方式、方法合并或構造出原問題的解。

不難發現，在分治策略中，由于子問題與原問題在結構和解法上的相似性，用分治方法解決的問題，大都采用了遞歸的形式。

在各種排序方法中，如歸并排序、堆排序、快速排序等，都存在有分治的思想。

分治算法的時間複雜度分析我們可以用遞推公式和遞歸樹。

一個分治法将規模為n的問題分成k個規模為n/m的子問題去解。

設分解閥值n0=1，且ADHOC§解規模為1的問題耗費1個單位時間。

再設将原問題分解為k個子問題以及用merge将k個子問題的解合并為原問題的解需用f(n)個單位時間。

用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

T（n）= k T(n/m) f(n)

通過叠代法求得方程的解：

遞歸方程及其解隻給出n等于m的方幂時T(n)的值，但是如果認為T(n)足夠平滑，那麼由n等于m的方幂時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調上升的，從而當 mi≤n由此可求得起時間複雜度為 O（nlogn）。

（1）二分搜索（查找）

（2）大整數乘法

（3）Strassen矩陣乘法

（4）棋盤覆蓋

（5）歸并排序

（6）快速排序

（7）線性時間選擇

（8）最接近點對問題

（9）循環賽日程表

（10）漢諾塔

二分查詢

二分查找是一種在每次比較之後将查找空間一分為二的算法，通過有序的區間可以直接确定結果在哪個區間，所以分的兩個區間隻需要計算其中一個區間，然後繼續進行一直到結束。

public int searchInsert(int[] nums, int target) { if(nums[0]>=target)return 0;//剪枝 if(nums[nums.length-1]==target)return nums.length-1;//剪枝 if(nums[nums.length-1]<target)return nums.length; int left=0,right=nums.length-1; while (left<right) { int mid=(left right)/2; if(nums[mid]==target) return mid; else if (nums[mid]>target) { right=mid; } else { left=mid 1; } } return left; }

快速排序

快排每一趟會選定一個數，将比這個數小的放左面，比這個數大的放右面，然後遞歸分治求解兩個子區間，當然快排因為在分的時候就做了很多工作，當全部分到最底層的時候這個序列的值就是排序完的值，這是一種分而治之的體現。

public void quicksort(int [] a,int left,int right) { int low=left; int high=right; //下面兩句的順序一定不能混，否則會産生數組越界！！！very important！！！ if(low>high)//作為判斷是否截止條件 return; int k=a[low];//額外空間k，取最左側的一個作為衡量，最後要求左側都比它小，右側都比它大。 while(low<high)//這一輪要求把左側小于a[low],右側大于a[low]。 { while(low<high&&a[high]>=k)//右側找到第一個小于k的停止 { high--; } //這樣就找到第一個比它小的了 a[low]=a[high];//放到low位置 while(low<high&&a[low]<=k)//在low往右找到第一個大于k的，放到右側a[high]位置 { low ; } a[high]=a[low]; } a[low]=k;//賦值然後左右遞歸分治求之 quicksort(a, left, low-1); quicksort(a, low 1, right); }

歸并排序(逆序數)

快排在分的時候做了很多工作，而歸并就是相反，歸并在分的時候按照數量均勻分，而合并時候已經是兩兩有序的進行合并的，因為兩個有序序列O(n)級别的複雜度即可得到需要的結果。而逆序數在歸并排序基礎上變形同樣也是分治思想求解。

private static void mergesort(int[] array, int left, int right) { int mid=(left right)/2; if(left<right) { mergesort(array, left, mid); mergesort(array, mid 1, right); merge(array, left,mid, right); } } private static void merge(int[] array, int l, int mid, int r) { int lindex=l;int rindex=mid 1; int team[]=new int[r-l 1]; int teamindex=0; while (lindex<=mid&&rindex<=r) {//先左右比較合并 if(array[lindex]<=array[rindex]) { team[teamindex ]=array[lindex ]; } else { team[teamindex ]=array[rindex ]; } } while(lindex<=mid)//當一個越界後剩餘按序列添加即可 { team[teamindex ]=array[lindex ]; } while(rindex<=r) { team[teamindex ]=array[rindex ]; } for(int i=0;i<teamindex;i ) { array[l i]=team[i]; } }

漢諾塔

漢諾塔的傳說

漢諾塔（又稱河内塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。

漢諾塔遊戲的演示和思路分析:

考慮最簡單情況n=2，三根柱子分别為A、B、C，此時，在A上有2片金片(假設從小到大依次為1,2)。

那麼我們的解決步驟可以歸結為如下：

1. 先把A上1号金片移至B。
2. 再把A上2号金片移至C。
3. 再把B上1号金片移至C。

考慮n增大的情況：

1. 先把A上從1到n-1号金片移至B。
2. 再把A上N号金片移至C。
3. 再把B上從1到n-1号金片移至C。

可以看到遞歸的影子，要解決n個，先解決n-1個，可以分治為n=2的最簡單情況并加以解決。

package com.qf.math; public class Hanoitower { public static void main(String[] args) { hanoitower(4,'A','B','C'); } public static void hanoitower(int num,char a,char b,char c){ if (num==1){ //盤數為1，做一次搬遷，從A移動到C柱 System.out.println("第1個盤從" a "移動到" c "盤"); }else{ //盤數大于1 //先從a盤最上面的盤值最下面的盤之間的所有盤，移動到b盤，C盤作為中間盤 hanoitower(num-1,a,c,b); //把最底下的那個盤，從a盤移動到c盤 System.out.println("第" num "個盤從" a "移動到" c "盤"); //把b盤的所有盤，移動到c盤上 hanoitower(num-1,b,a,c); } } }

最大子序列和

最大子序列和的問題我們可以使用動态規劃的解法，但是也可以使用分治算法來解決問題，但是最大子序列和在合并的時候并不是簡單的合并，因為子序列和涉及到一個長度的問題，所以正确結果不一定全在最左側或者最右側，而可能出現結果的區域為：

• 完全在中間的左側
• 完全在中間的右側
• 包含中間左右兩個節點的一個序列

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

public int maxSubArray(int[] nums) { int max=maxsub(nums,0,nums.length-1); return max; } int maxsub(int nums[],int left,int right) { if(left==right) return nums[left]; int mid=(left right)/2; int leftmax=maxsub(nums,left,mid);//左側最大 int rightmax=maxsub(nums,mid 1,right);//右側最大 int midleft=nums[mid];//中間往左 int midright=nums[mid 1];//中間往右 int team=0; for(int i=mid;i>=left;i--) { team =nums[i]; if(team>midleft) midleft=team; } team=0; for(int i=mid 1;i<=right;i ) { team =nums[i]; if(team>midright) midright=team; } int max=midleft midright;//中間的最大值 if(max<leftmax) max=leftmax; if(max<rightmax) max=rightmax; return max; }

分治法實際上就是類似于數學歸納法，找到解決本問題的求解方程公式，然後根據方程公式設計遞歸程序。 一定是先找到最小問題規模時的求解方法，然後考慮随着問題規模增大時的求解方法找到求解的遞歸函數式後（各種規模或因子），設計遞歸程序即可。

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