分治算法与典型例题

目录

前言

一、分治算法要素（条件）

二、分治算法设计步骤

三、时间复杂度求解

四、典型例题1——归并排序

五、典型例题2——快速排序

总结

 

---

前言

          在算法设计中，引入分而治之的策略，称为分治算法。其本质是将大规模问题分解为若干个规模较小的相同子问题，分而治之。举出两个典型例子，这里只放伪代码，具体内容可以参看《趣学算法》。

---

一、分治算法要素（条件）

        1.原问题可以分解为若干个规模较小的相同子问题。

        2.子问题相互独立。

        3.子问题的解可以合并为原问题的解。

二、分治算法设计步骤

        一般步骤如下：

        1.分解，将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

        2.治理，求解各个子问题。由于子问题与原问题形式相同，只是规模较小，当规模足够小时，就可以用较简单的方法解决。

        3.合并，按原问题要求，将子问题的解逐层合并构成原问题的解。

        分治算法中，各个子问题形式相同，解决方法一样，因此可以用递归算法快速解决。

三、时间复杂度求解

        主要有三种方法，递推式法、递归树法和通式法。这里主要讲通式法。

通式法：

        用T(n)表示分治法解决规模为n的问题所需要的时间，

        可以用递推树法证明，

1 \\ O(n^d\log_b n), a/b^d = 1 \end{matrix}\right." src="https://latex.codecogs.com/gif.latex?T%28n%29%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20O%28n%5Ed%29%20%2C%20a/b%5Ed%20%3C%201%20%5C%5C%20O%28n%5E%7B%5Clog_b%20a%7D%29%2C%20a/b%5Ed%20%3E%201%20%5C%5C%20O%28n%5Ed%5Clog_b%20n%29%2C%20a/b%5Ed%20%3D%201%20%5Cend%7Bmatrix%7D%5Cright." />

        例，求解下式的时间复杂度，（一般情况下快速排序时间复杂度）

        a=2, b=2, d=1, =1, 则

四、典型例题1——归并排序

伪代码

void Merge(int A[], int low, int mid, int high)
{
    //申请一个辅助数组，归并排序是异地稳定排序
    int *B = new int [high-low+1];
    int i = low, j = mid + 1, k = 0;
    while(i <= mid && j <= high)
    {
        //从小到大把数据存入B[]
        if(A[i] <= A[j])
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }
    while(i <= mid) B[k++] = A[i++];//处理剩余A[low, mid]
    while(j <= high) B[k++] = A[j++];//处理剩余A[mid+1, high]
    for(i = low, k = 0; i <= high; i++)
    {
        A[i] = B[k++];
    }
}

void MergeSort(int A[], int low, int high)
{
    if(low < high)
    {
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A, low, mid, high);
    }
}

        时间复杂度。

五、典型例题2——快速排序

伪代码

int Partition(int r[], int low, int high)
{
    int i = low, j = high, pivot = r[low];//基准元素取第一个，也有首元素，尾元素，中间元素三者取中值
    while(i < j)
    {
        while(i < j && r[j] > pivot) j--;//向左扫描
        if(i < j) swap(r[i++], r[j]);//交换i，j，并且i右移一位
        
        //反向过程
        while(i < j && r[i] <= pivot) i++;//向右扫描
        if(i < j) swap(r[i], r[j--]);//交换i，j，并且j左移一位
    }
    //找到pivot的位置并返回
    return i;
}

void QuickSort(int R[], int low, int high)
{
    if(low < high)
    {
        int mid = Partition(R, low, high);
        QuickSort(R, low, mid-1);
        QuickSort(R, mid+1, high);
    }
}

        快速排序本地不稳定排序，性能不一定比归并排序好，一般情况下时间复杂度，最差情况下时间复杂度。STL中的sort()函数融合多种排序算法，快速排序不一定最佳，需看具体情况。

---

总结

        分治算法最大优势可以使用递归程序实现，编程简单，但是分解、治理过程有很大技巧，不易掌握。这里例1主要难在合并过程，例2难在分解过程，这两类程序框架可以不止用于排序算法。