分治算法

分治法

1.什么是分治算法？

将原问题划分成n个小规模的问题，并且这些小规模问题与原问题结构相似，递归去解决这些子问题，最后合并子问题的结果，就得到了原问题的解。

2.分治基本操作步骤？

• 分解：将原问题分解为一系列子问题
• 解决：递归解决子问题，当子问题足够小，直接求解
• 合并：将子问题的解合并原问题的解。

3.分治算法需要满足的条件?

• 原问题与分解的小问题具有相同的结构
• 原问题分解的子问题之间无联系(和动态规划的直接区别)
• 具有终止分解的条件，问题分解到一定规模，停止，并可以求解
• 子问题的解可以合并原问题。

4.快速排序和归并排序

前面排序章节二我已经细讲了两种排序算法实现思想，这里只是谈谈它如何用到了分治思想。没懂这两个算法的，可以去看看我前面的资料。

首先是快速排序，它将原问题划分成一个个小问题，每次递归分区操作，每次分区都会确定一个基准值，基准值左边都小于基准数，基准值右边都大于这个基准数。当递归到数组里只剩一个数据时，那数据肯定有序了，然后递归逐层返回有序的数据，这就是典型的分治。

接着是归并排序，这个更简单，每次将数组分成两半，前半部分和后半部分，逐层递归分解，直到数组只剩一个数据停止(1个数据肯定有序了)，然后递归带回，逐层的合并，就是归并数据，每层都有序了，最终数组就有序了，还是分治的思想。

5.用分治思想求数组最大值

分析：每次将数组递归分解成两半，前半部分和后半部分，只剩一个数据，这个数据就是最大的，然后数据合并同时，比较最大值，最后一层合并，就是整个数组的最大值

int findMax(int *arr,int low,int high)
{
    int max,mid,max1,max2;
    mid = (low+high)/2;
    //数组只有一个数据，它就是最大的
    if(low==high)
    {
        max = arr[low];
        return max;
    }
    //数组数据大于等于2个，那个左半分区和右半分区最大值比较
    else
    {
        max1 = findMax(arr,low,mid);
        max2 = findMax(arr,mid+1,high);
        return max1>max2? max1:max2;
    }
}

上面我就用到了分治思想，首先将问题递归划分成小规模数据，直到规模变成1，此时它就是最大值，然后归并数据时，两两比较大小，最后一层返回的就是最大值。

6.用分治思想求折半查找

分析：普通版本的折半查找我们很清楚，那如何用分治去实现？和普通版一样，每次对比中间数据，中间数据比目标查找值大，递归去左边找，反之去右边，递归退出的条件是找到了或者数据不存在。

int findNum(int *arr,int num,int low,int high)
{
    if(low>high)
    {
        return -1;
    }
    int mid;
    mid = (low+high)/2;
    if(arr[mid]==num)
    {
        return mid;
    }else if(arr[mid]<num)
    {
        return findNum(arr,num,mid+1,high);
    }else
    {
        return findNum(arr,num,low,mid);
    }
}

获取完整代码

我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。

点击查看