[[355166]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai 。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

分治算法(divide and conquer)是五大常用算法(分治算法、動態(tài)規(guī)劃算法、貪心算法、回溯法、分治界限法)之一，很多人在平時學(xué)習(xí)中可能只是知道分治算法，但是可能并沒有系統(tǒng)的學(xué)習(xí)分治算法，本篇就帶你較為全面的去認(rèn)識和了解分治算法。

在學(xué)習(xí)分治算法之前，問你一個問題，相信大家小時候都有存錢罐的經(jīng)歷，父母親人如果給錢都會往自己的寶藏中存錢，我們每隔一段時間都會清點清點錢。但是一堆錢讓你處理起來你可能覺得很復(fù)雜，因為數(shù)據(jù)相對于大腦有點龐大了，并且很容易算錯，你可能會將它先分成幾個小份算，然后再疊加起來計算總和就獲得這堆錢的總數(shù)了

當(dāng)然如果你覺得各個部分錢數(shù)量還是太大，你依然可以進(jìn)行劃分然后合并，我們之所以這么多是因為：

計算每個小堆錢的方式和計算最大堆錢的方式是相同的(區(qū)別在于體量上)

然后大堆錢總和其實就是小堆錢結(jié)果之和。這樣其實就有一種分治的思想。

當(dāng)然這些錢都是想出來的……

分治算法介紹

分治算法是用了分治思想的一種算法，什么是分治?

分治，字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。在計算機(jī)科學(xué)中，分治法就是運用分治思想的一種很重要的算法。分治法是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)等等。

將父問題分解為子問題同等方式求解，這和遞歸的概念很吻合，所以在分治算法通常以遞歸的方式實現(xiàn)(當(dāng)然也有非遞歸的實現(xiàn)方式)。分治算法的描述從字面上也很容易理解，分、治其實還有個合并的過程：

• 分(Divide)：遞歸解決較小的問題(到終止層或者可以解決的時候停下)
• 治(Conquer)：遞歸求解，如果問題夠小直接求解。
• 合并(Combine)：將子問題的解構(gòu)建父類問題

一般分治算法在正文中分解為兩個及以上的遞歸調(diào)用，并且子類問題一般是不相交的(互不影響)。當(dāng)求解一個問題規(guī)模很大很難直接求解，但是規(guī)模較小的時候問題很容易求解并且這個問題并且問題滿足分治算法的適用條件，那么就可以使用分治算法。

那么采用分治算法解決的問題需要 滿足那些條件(特征) 呢?

1 . 原問題規(guī)模通常比較大，不易直接解決，但問題縮小到一定程度就能較容易的解決。

2 . 問題可以分解為若干規(guī)模較小、求解方式相同(似)的子問題。且子問題之間求解是獨立的互不影響。

3 . 合并問題分解的子問題可以得到問題的解。

你可能會疑惑分治算法和遞歸有什么關(guān)系?其實分治重要的是一種思想，注重的是問題分、治、合并的過程。而遞歸是一種方式(工具)，這種方式通過方法自己調(diào)用自己形成一個來回的過程，而分治可能就是利用了多次這樣的來回過程。

分治算法經(jīng)典問題

對于分治算法的經(jīng)典問題，重要的是其思想，因為我們大部分借助遞歸去實現(xiàn)，所以在代碼實現(xiàn)上大部分都是很簡單，而本篇也重在講述思想。

分治算法的經(jīng)典問題，個人將它分成兩大類：子問題完全獨立和子問題不完全獨立。

1 . 子問題完全獨立就是原問題的答案可完全由子問題的結(jié)果推出。

2 . 子問題不完全獨立，有些區(qū)間類的問題或者跨區(qū)間問題使用分治可能結(jié)果跨區(qū)間,在考慮問題的時候需要仔細(xì)借鑒下。

二分搜索

二分搜索是分治的一個實例，只不過二分搜索有著自己的特殊性

• 序列有序
• 結(jié)果為一個值

正常二分將一個完整的區(qū)間分成兩個區(qū)間，兩個區(qū)間本應(yīng)單獨找值然后確認(rèn)結(jié)果，但是通過有序的區(qū)間可以直接確定結(jié)果在哪個區(qū)間，所以分的兩個區(qū)間只需要計算其中一個區(qū)間，然后繼續(xù)進(jìn)行一直到結(jié)束。實現(xiàn)方式有遞歸和非遞歸，但是非遞歸用的更多一些：

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

 快速排序

快排也是分治的一個實例，快排每一趟會選定一個數(shù)，將比這個數(shù)小的放左面，比這個數(shù)大的放右面，然后遞歸分治求解兩個子區(qū)間，當(dāng)然快排因為在分的時候就做了很多工作，當(dāng)全部分到最底層的時候這個序列的值就是排序完的值。這是一種分而治之的體現(xiàn)。

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

 歸并排序(逆序數(shù))

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

 

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)//當(dāng)一個越界后剩余按序列添加即可 
  { 
    team[teamindex++]=array[lindex++]; 
 
  } 
  while(rindex<=r) 
  { 
    team[teamindex++]=array[rindex++]; 
  }  
  for(int i=0;i<teamindex;i++) 
  { 
    array[l+i]=team[i]; 
  } 
} 

 最大子序列和

最大子序列和的問題我們可以使用動態(tài)規(guī)劃的解法，但是也可以使用分治算法來解決問題，但是最大子序列和在合并的時候并不是簡單的合并，因為子序列和涉及到一個長度的問題，所以正確結(jié)果不一定全在最左側(cè)或者最右側(cè)，而可能出現(xiàn)結(jié)果的區(qū)域為：

• 完全在中間的左側(cè)
• 完全在中間的右側(cè)
• 包含中間左右兩個節(jié)點的一個序列

用一張圖可以表示為：

所以在具體考慮的時候需要將無法遞歸得到結(jié)果的中間那個最大值串的結(jié)果也算出來參與左側(cè)、右側(cè)值得比較。

力扣53. 最大子序和在實現(xiàn)的代碼為：

ublic 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);//左側(cè)最大 
    int rightmax=maxsub(nums,mid+1,right);//右側(cè)最大 
 
    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; 
} 

 最近點對

最近點對是一個分治非常成功的運用之一。在二維坐標(biāo)軸上有若干個點坐標(biāo)，讓你求出最近的兩個點的距離，如果讓你直接求那么枚舉暴力是個非常非常大的計算量,我們通常采用分治的方法來優(yōu)化這種問題。

如果直接分成兩部分分治計算你肯定會發(fā)現(xiàn)如果最短的如果一個在左一個在右會出現(xiàn)問題。我們可以優(yōu)化一下。

在具體的優(yōu)化方案上，按照x或者y的維度進(jìn)行考慮，將數(shù)據(jù)分成兩個區(qū)域，先分別計算(按照同方法)左右區(qū)域內(nèi)最短的點對。然后根據(jù)這個兩個中較短的距離向左和向右覆蓋，計算被覆蓋的左右點之間的距離，找到最小那個距離與當(dāng)前最短距離比較即可。

這樣你就可以發(fā)現(xiàn)就這個一次的操作(不考慮的情況)，左側(cè)紅點就避免和右側(cè)大部分紅點進(jìn)行距離計算(O(n2)的時間復(fù)雜度)。事實上，在進(jìn)行左右區(qū)間內(nèi)部計算的時候，它其實也這樣遞歸的進(jìn)行很多次分治計算。如圖所示：

 

這樣下去就可以節(jié)省很多次的計算量。

但是這種分治會存在一種問題就是二維坐標(biāo)可能點都聚集某個方法某條軸那么可能效果并不明顯(點都在x=2附近對x分割作用就不大)，需要注意一下。

杭電1007推薦給大家，ac的代碼為：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.io.PrintWriter; 
import java.io.StreamTokenizer; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Comparator; 
import java.util.List; 
public class Main { 
    static int n; 
    public static void main(String[] args) throws IOException { 
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); 
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); 
        //List<node>list=new ArrayList(); 
         while(in.nextToken()!=StreamTokenizer.TT_EOF) 
         { 
             n=(int)in.nval;if(n==0) {break;} 
            node no[]=new node[n]; 
             
             for(int i=0;i<n;i++) 
             { 
                 in.nextToken();double x=in.nval; 
                 in.nextToken();double y=in.nval; 
                // list.add(new node(x,y)); 
                 no[i]=new node(x,y); 
             } 
             Arrays.sort(no, com); 
            double min= search(no,0,n-1); 
            out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush(); 
         }          
    } 
    private static double search(node[] no, int left,int right) { 
        int mid=(right+left)/2; 
        double minleng=0; 
        if(left==right) {return Double.MAX_VALUE;} 
        else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);} 
        else minleng= min(search(no,left,mid),search(no,mid,right)); 
        int ll=mid;int rr=mid+1; 
        while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;} 
        while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;} 
        for(int i=ll;i<rr;i++) 
        { 
            for(int j=i+1;j<rr+1;j++) 
            { 
                double team=0; 
                if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;} 
                else 
                {  
                    team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y); 
                    if(team<minleng)minleng=team; 
                } 
            } 
        } 
        return minleng; 
     
    } 
    private static double min(double a, double b) { 
        // TODO 自動生成的方法存根 
        return a<b?a:b; 
    } 
    static Comparator<node>com=new Comparator<node>() { 
 
        @Override 
        public int compare(node a1, node a2) { 
            // TODO 自動生成的方法存根 
            return a1.y-a2.y>0?1:-1; 
        }}; 
    static class node 
    { 
        double x; 
        double y; 
        public node(double x,double y) 
        { 
            this.x=x; 
            this.y=y; 
        } 
    } 
} 

 結(jié)語

到這里，分治算法就講這么多了，因為分治算法重要在于理解其思想，還有一些典型的分治算法解決的問題，例如大整數(shù)乘法、Strassen矩陣乘法、棋盤覆蓋、線性時間選擇、循環(huán)賽日程表、漢諾塔等問題你可以自己研究其分治的思想和原理。

原文鏈接：https://mp.weixin.qq.com/s/jHiBOjfyMvuvGzSecsdNPw