【算法】-----分治篇-----

大家好，这里是彤砸！

今天给大家讲讲分治

分治，是将一个先分解成若干个子问题，递归求解每个子问题后，再将这若干个子问题的解综合得到原问题的解

分治适用的条件要满足：

1. 该问题的规模缩小到一定的程度时可容易求解
2. 该问题可以分解为若干规模较小的相同的子问题
3. 子问题的解可以合并成原问题的解（这一点很重要）
4. 各个子问题是相互独立的，没有关联

再给大家讲讲——

分治法的应用，分为三个——

1. 归并排序
2. 快速排序
3. 二分查找

归并排序嘛……

先给大家康康分治算法的伪码——

      MergeSort(A,p,r) //归并排序数A[p..r], 1<=p<=r<=n
       if p<r  then q<-(p+r)/2
       MergeSort(A,p,q)   
       MergeSort(A,q+1,r)
       Merge(A,p,q,r) 

思想呢，大概就是——

二路归并

这个嘛。。懂的都懂，不懂得就别找我了行不行求求了

接下来我们进行算法改进——

消除递归

就是上面这个样子

再就是快速排序（反正我就叫它快排）

先看算法伪码——

输入：数组A[p…r]        p=1, r=n
输出：排好序的数组A
             if  p < r    then q<-Partition(A, p, r)
              A[p]A[q]
                     Quicksort(A,p,q-1)
                      Quicksort(A,q+1,r)

再说说时间复杂度：

我们要考虑到——

1. 最坏情况
2. 最好情况
3. 平均情况
4. 能否改进？

给大家一张图——

这是几种常见排序的时间复杂度。

最后是二分查找 

就给大家一个模板吧——

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

好啦，小结一下

本章我们讲了：

                分治算法的设计思想；

                分治算法的举例；

                分治算法时间复杂度的改进

就这样吧，拜拜！

                                                                                                                        记得三连QAQ！！！