五大基本算法之分治算法

责编：顶级算法 | 来源：houbb
houbb.github.io/2020/01/23/data-struct-learn-07-base-divided
上一篇精彩：火遍全国的网络热梗“yyds”，创造者被判刑3年

大家好，我是顶级算法。

【前言】：分治算法，与其说是一种算法，不如说是一种思想，这种思想在计算机的很多算法中，都有所体现，那么让我们一起来学习下这种思想吧，也看看在算法中是怎么体现出这种思想的。

分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
基本思想
当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。
对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。
如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。
这就是分治策略的基本思想。
二分法
利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。
分治法解题的一般步骤： 
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
应用场景 运用分治策略解决的问题一般来说具有以下特点：
1、原问题可以分解为多个子问题
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2、原问题在分解过程中，递归地求解子问题
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
3、在求解并得到各个子问题的解后
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。
在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
分治算法的时间复杂度
分治算法的时间复杂度分析我们可以用递推公式和递归树。
例如：一个规模为n的问题，每次将其分解为k个子问题，直至子问题的规模为1,合并k个子问题的时间复杂度为O(n).
则原问题的时间复杂度T(n)=kT(n/k)+O(n).
由此可求得起时间复杂度为 O（nlogn）.
搜索公众号顶级算法回复“算法心得”，送你一份惊喜礼包。
经典问题
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
合并排序
/*************************************
*
* Megre_Sort()
* 输入:两个数组及长度
*************************************/
void Megre_sort(int *A,int p,int *C,int q)
{
    int *B; 
    int s=0,t=0,k=0,i = 0,r=p+q;
    B = (int *)malloc(sizeof(int)*(p+q));
 
    while( s <= p && t <= q )
    {
        if(A[s] <= C[t])
        {
            B[k] = A[s];
            s++;
        }
        else
        {
            B[k] = C[t];
            t++;
        }
        k++;
    }
    if (s = q +1)
    for( i = 0; i <= (r-k);i++)
        B[k+i] = C[t+i];
    else
        for( i = 0; i <= (r-k);i++)
            B[k+i] = A[s+i];
    for(i = 0; i < p+q ; i++)
    {
       printf("%d ",B[i]);
    }
}
/*************************************
*
* BottomUp_Sort()
* 输入:数组及长度
*************************************/
void BottomUp_Sort(int n)
{
    int i = 1,s,j;
    int *A;
    A = (int*)malloc(sizeof(int)*n);
    srand( (unsigned)time( NULL ) );  
    for(i = 0;i < n; i ++)
    {
        A[i] = rand();
    }
    while ( i < n)
    { 
        s = i;
        i = 2*s;
        j = 0;
        while ( j + i <= n)
        {
            Megre_sort(A,s,A+s,i);
            j++;
      }
      if ( j + s < n)
     Megre_sort(A,s,A+s,n-j);
   }
}
快速排序
/*************************************
*
* Quick_Sort()
* 输入:数组及长度
*************************************/
void Quick_Sort(int *A,int low,int high)
{
 
    if (A == NULL || low >= high)
        return ;
    int part = SPLIT(A, low, high);
    Quick_Sort(A, low, part-1);
    Quick_Sort(A, part+1, high);
    
   
}
/*************************************
*
* SPLIT()
* 输入:划分数组 
*************************************/
int SPLIT(int *a, int beg, int end)
{
    int i,c,x,j;
    i = beg;
    x = a[beg];
    for(j = beg+1; j <= end; ++j)
    {
        if(a[j] <= x)
        {
            ++i;
            if(i != j)
            {
                c= a[i];
                a[i]=a[j];
                a[j] =c;
            }    
        }
    }
    x = a[beg];
    a[beg]=a[i];
    a[i] = x;
    return i;
}
个人收获
Map-Reduce 是类似的思想
多线程甚至也可以理解为分治的思想。

觉得不错？欢迎转发分享给更多人

如何有效地做算法题？
算法分析的正确姿势
上午写了一段代码，下午就被开除了，奇怪的知识又增加了…
面试时写不出排序算法？看这篇就够了
一招减少 JavaScript 代码量！
五大常用算法：贪心算法
算法的时间复杂度和空间复杂度