关于算法:五大常用算法一文搞懂分治算法

原创公众号：bigsai
文章收录在 bigsai-algorithm

前言

分治算法（divide and conquer）是五大罕用算法 (分治算法、动静布局算法、贪婪算法、回溯法、分治界线法) 之一，很多人在平时学习中可能只是晓得分治算法，然而可能并没有零碎的学习分治算法，本篇就带你较为全面的去意识和理解分治算法。

在学习分治算法之前，问你一个问题，置信大家小时候都有存钱罐的经验，父母亲人如果给钱都会往本人的宝藏中存钱，咱们每隔一段时间都会盘点盘点钱。然而一堆钱让你解决起来你可能感觉很简单，因为数据绝对于大脑有点宏大了，并且很容易算错，你可能会将它 先分 成几个小份算，而后 再叠加 起来计算总和就取得这堆钱的总数了

当然如果你感觉各个局部钱数量还是太大，你仍然能够进行划分而后合并，咱们之所以这么多是因为：

• 计算每个小堆钱的形式和计算最大堆钱的形式是雷同的(区别在于体量上)
• 而后大堆钱总和其实就是小堆钱后果之和。这样其实就有一种分治的思维。

当然这些钱都是想进去的……

分治算法介绍

分治算法是用了分治思维的一种算法，什么是分治？

分治，字面上的解释是“分而治之”，就是把一个简单的问题分成两个或更多的雷同或类似的子问题，再把子问题分成更小的子问题……直到最初子问题能够简略的间接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是使用分治思维的一种很重要的算法。分治法是很多高效算法的根底，如排序算法（疾速排序，归并排序），傅立叶变换（疾速傅立叶变换）等等。

将父问题合成为子问题等同形式求解，这和递归的概念很吻合，所以在分治算法通常以递归的形式实现(当然也有非递归的实现形式)。分治算法的形容从字面上也很容易了解，分、治其实还有个合并的过程：

• 分(Divide)：递归解决较小的问题(到终止层或者能够解决的时候停下)
• 治(Conquer)：递归求解，如果问题够小间接求解。
• 合并(Combine)：将子问题的解构建父类问题

个别分治算法在注释中合成为两个即以上的递归调用，并且子类问题个别是不想交的(互不影响)。当求解一个问题规模很大很难间接求解，然而规模较小的时候问题很容易求解并且这个问题并且问题满足分治算法的实用条件，那么就能够应用分治算法。

那么采纳分治算法解决的问题须要 满足那些条件(特色) 呢?

1 . 原问题规模通常比拟大，不易间接解决，但问题放大到肯定水平就能较容易的解决。

2 . 问题能够合成为若干规模较小、求解形式雷同 (似) 的子问题。且子问题之间求解是独立的互不影响。

3 . 合并问题合成的子问题能够失去问题的解。

你可能会纳闷分治算法和递归有什么关系？其实分治重要的是一种思维，重视的是问题分、治、合并的过程。而递归是一种形式(工具)，这种形式通过办法本人调用本人造成一个来回的过程，而分治可能就是利用了屡次这样的来回过程。

分治算法经典问题

对于分治算法的经典问题，重要的是其思维，因为咱们大部分借助递归去实现，所以在代码实现上大部分都是很简略，而本篇也重在讲述思维。

分治算法的经典问题，集体将它分成两大类：子问题齐全独立和子问题不齐全独立。

1 . 子问题齐全独立就是原问题的答案可齐全由子问题的后果推出。

2 . 子问题不齐全独立，有些区间类的问题或者跨区间问题应用分治可能后果跨区间, 在思考问题的时候须要认真借鉴下。

二分搜寻

二分搜寻是分治的一个实例，只不过二分搜寻有着本人的特殊性

• 序列有序
• 后果为一个值

失常二分将一个残缺的区间分成两个区间，两个区间本应独自找值而后确认后果，然而通过有序的区间能够间接确定后果在那个区间，所以分的两个区间只须要计算其中一个区间，而后持续进行始终到完结。实现形式有递归和非递归，然而非递归用的更多一些：

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

最大子序列和

最大子序列和的问题咱们能够应用动静布局的解法，然而也能够应用分治算法来解决问题，然而最大子序列和在合并的时候并不是简略的合并，因为子序列和波及到一个长度的问题，所以正确后果不肯定全在最左侧或者最右侧，而可能呈现后果的区域为：

• 齐全在两头的左侧
• 齐全在两头的右侧
• 蕴含两头左右两个节点的一个序列

用一张图能够示意为：

所以在具体思考的时候须要将无奈递归失去后果的两头那个最大值串的后果也算进去参加左侧、右侧值得比拟。

力扣 53. 最大子序和在实现的代码为：

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

最近点对

最近点对是一个分治十分胜利的使用之一。在二维坐标轴上有若干个点坐标，让你求出最近的两个点的间隔，如果让你间接求那么枚举暴力是个十分十分大的计算量, 咱们通常采纳分治的办法来优化这种问题。

如果间接分成两局部分治计算你必定会发现如果最短的如果 一个在左一个在右会呈现问题。咱们能够优化一下。

在具体的优化计划上，依照 x 或者 y 的维度进行思考，将数据分成两个区域，先别离计算 (依照同办法) 左右区域内最短的点对。而后依据这个两个中较短的间隔向左和向右笼罩，计算被笼罩的左右点之间的间隔，找到最小那个间隔与以后最短距离比拟即可。

这样你就能够发现就这个一次的操作 (不思考子状况)，左侧红点就防止和右侧大部分红点进行间隔计算(O(n2) 的工夫复杂度)。事实上，在进行左右区间外部计算的时候，它其实也这样递归的进行很屡次分治计算。如图所示：

这样上来就能够节俭很屡次的计算量。

然而这种分治会存在一种问题就是二维坐标可能点都汇集某个办法某条轴那么可能成果并不显著(点都在 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;
        }
    }
}

结语

到这里，分治算法就讲这么多了，因为分治算法重要在于了解其思维，还有一些典型的分治算法解决的问题，例如大整数乘法、Strassen 矩阵乘法、棋盘笼罩、线性工夫抉择、循环赛日程表、汉诺塔等问题你能够本人钻研其分治的思维和原理。

原创不易，bigsai 请你帮两件事帮忙一下:

1. 点赞在看，您的必定是我在思否创作的源源能源。
2. 微信搜寻「bigsai」，新人求关注~