算法复习-分治算法

基本思想

先来看一个经典的二分查找例子。

int binarySearch(vector<int>& nums, int target)
{
    int n = nums.size();
    int left = 0, right = n - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(target == nums[mid]) return mid;
        else if(target > nums[mid]) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

时间复杂度是$O(logn)$。

我们看到，二分查找贯彻了分治的思想。当我们要解决一个输入规模较大(不妨设为$n$)的问题时，可以将这个问题分解成$k$个不同的子集，如果能得到$k$个不同的、可以独立求解的子问题，而且在求出解之后还可以使用适当的方法将他们的解合并成整个问题的解，这样原问题得以解决，这种将整个问题分解成若干小问题处理的方法称为分治法。

一般来说：

1. 分解出的子问题应与原问题有相同的结构(便于使用递归实现)。
2. 如果分解出的子问题仍然很大，可以对子问题继续使用分治法，直到子问题不用分解就可以直接求解。
3. 一般情况下，$k=2$是一个常见的思路。

下面是分治法一般的伪代码：

DiCo(p, q)
{
    global n, A[1,...,n];
    integer m, p, q;
    if(small(p, q)) return solve(p, q);
    else
    {
        m = divide(p, q);
        return (combine(DiCo(p, m), DiCo(m+1, q)));
    }
}

• small(p, q) return bool：判断当前的子问题是否还需要细分
• solve(p, q)：对可以直接求解的子问题的求解函数
• divide(p, q) return int: 决定当前问题的分割点
• combine(p, q): 合成函数，用来合成两个子问题的解

一些例子

本节中我们主要分析一些使用分治算法的例子。

求最大最小值

问题描述：求一个n元数组中的最大值和最小值
 
输入：[2,4,1,6,4,3,2,-1]
 
输出：[-1,6]

一个最基本的思路是这样的：

vector<int> maxmin(vector<int>& nums)
{
    if(nums.empty()) return {};
    int fmax = nums[0], fmin = nums[0];
    for(int i = 1 ; i < nums.size() ; ++i)
    {
        if(nums[i] > fmax) fmax = nums[i];
        if(nums[i] < fmin) fmin = nums[i];
    }
    return {fmin, fmax};
}

不难得到，在最好、最坏情况下的比较次数均为$2(n-1)$，平均比较次数也是$2(n-1)$。

因为$nums[i]$不可能既大于$fmax$，又小于$fmin$，所以可以做出如下修改：

vector<int> maxmin(vector<int>& nums)
{
    if(nums.empty()) return {};
    int fmax = nums[0], fmin = nums[0];
    for(int i = 1 ; i < nums.size() ; ++i)
    {
        if(nums[i] > fmax) fmax = nums[i];
        else if(nums[i] < fmin) fmin = nums[i];
    }
    return {fmin, fmax};
}

这样，最好、最坏情况的比较次数分别是$n-1$，$2(n-1)$，平均比较次数是$3(n-1)/2$。这里的最好情况是数组递增，最坏情况是数组递减。

好像看到现在跟分治没什么关系QAQ。那么这个问题用分治的思想如何解决呢？不难理解，求$n$元数组的最大最小值，可以转换为分别求两个$n/2$数组的最大最小值，然后在得出的两个最小值里取最小、最大值里取最大，即可求出整个数组的最大最小值，我们可以将子问题分解为大小为1或2，这样可以直接求出最大最小值。

经过上面的分析，不难写出代码：

vector<int> maxmin(vector<int>& nums, int start, int end)
{
    int fmax = 0, fmin = 0;
    if(start == end)
    {
        fmax = fmin = nums[start];
    }
    else if(start == end - 1)
    {
        if(nums[start] > nums[end])
        {
            fmax = nums[start];
            fmin = nums[end];
        }
        else
        {
            fmax = nums[end];
            fmin = nums[start];
        }
    }
    else
    {
        int mid = start + (end - start) / 2;
        vector<int> left = maxmin(nums, start, mid);
        vector<int> right = maxmin(nums, mid+1, end);
        fmax = max(left[1], right[1]);
        fmin = min(left[0], right[0]);
    }
    return {fmin, fmax};
}

我们可以分析出比较次数，设$T(n)$表示比较次数，那么递推关系式为：

$$T(n) = \left\{ \begin{array}{l} 0,n = 1\\ 1,n = 2\\ T(\left\lfloor {n/2} \right\rfloor ) + T(\left\lceil {n/2} \right\rceil ) + 2,n > 2 \end{array} \right.$$

不妨令$n=2^k$，则有：

$$\begin{array}{l} T(n) = 2T(n/2) + 2\\ T(n) = {2^{k - 1}}T(2) + \sum\limits_{i = 1}^{k - 1} { {2^i}} \\ T(n) = {2^{k - 1}} + 2({2^{k - 1}} - 1) = 3n/2 - 2 \end{array}$$

无论是哪种情况，比较次数均为$3n/2-2$，实际上，任何一种以元素比较为基础的最大最小算法，其比较次数下界为$T(n) = \left\lceil {3n/2} \right\rceil - 2$，所以分治的最大最小算法是最优的。但是需要$\left\lfloor {logn} \right\rfloor + 1$层递归，需要占用较多的内存空间，同时元素出入栈也会带来时间开销，所以分治求最大最小值未必比直接求最大最小值效率高。举这个例子主要是解释分治的思想。

搜索算法的时间下界

任何一种以比较为基础的搜索算法，其最坏情况用时不可能低于$\Theta(logn)$。不存在最坏情况下时间比二分查找数量级还低的算法。因为二分查找产生的二叉搜索树使得比较树的深度最低，所以二分查找是搜索问题在最坏情况下的最好方法。

这里的最坏情况是指搜索边界值的情况，而且这里的数组是排好序的升序数组。

归并排序算法

我们先看一个永远不会单独使用，但是却经常被拿出来批判一番的插入排序hhh。插入排序的思想是将一个数字插入当前的有序数组中，使得插入后的数组依旧有序。代码如下：

void insort(vector<int>& nums)
{
    for(int i = 1 ; i < nums.size() ; ++i)
    {
        int temp = nums[i];
        int j;
        for(j = i - 1 ; j >= 0 ; --j)
        {
            if(temp < nums[j])
            {
                nums[j+1] = nums[j];
            }
        }
        nums[j+1] = temp;
    }
}

最坏的情况下是排一个逆序的数组，所以时间复杂度为$\Theta(n^2)$。我们不难发现，大部分时间都花费在移动元素上，而且同一个元素在排序过程中被挪动不止一次。

那么，怎样用分治的思路解决这个问题呢？一种思路是将要排序的数组分成两个子数组，分别对这两个子数组排序，再将这两个排好序的子数组合并起来，可以写出如下的代码：

vector<int> nums{2,3,3,4,1,0,8,67,5,33,22,534,123,1,-1,45,33,6,7,4,0,8,79,3,45};
vector<int> temp(nums.begin(), nums.end());
void mergesort(int start, int end)
{
    if(start >= end) return;
    int mid = start + (end - start) / 2;
    mergesort(start, mid);
    mergesort(mid+1, end);
    merge(start, end);
}
void merge(int start, int end)
{
    int mid = start + (end - start) / 2;
    int i = start, j = mid + 1, k = start;
    while(i <= mid && j <= end)
    {
        if(nums[i] < nums[j])
        {
            temp[k] = nums[i];
            ++i;
        }
        else
        {
            temp[k] = nums[j];
            ++j;
        }
        ++k;
    }
    if(i > mid)
    {
        while(j <= end)
            temp[k++] = nums[j++];
    }
    else if(j > end)
    {
        while(i <= mid)
            temp[k++] = nums[i++];
    }
    for(int p = start ; p <= end ; ++p)
    {
        nums[p] = temp[p];
    }
}

类似地，可以得到时间复杂度是$O(nlogn)$。

同时有如下结论：$\Theta(nlogn)$是以比较为基础的排序算法最坏情况下的时间下界。

可见从时间复杂度来看，归并排序是时间复杂度最低的排序算法。但是归并排序还存在一些问题：

1. 归并排序一直分解到一个元素，实际上当元素较少时，直接排序要比归并排序花费的时间少，因为归并排序不可避免的要对元素进行拆分合并。

2. 归并排序中会借用一个临时数组$temp$存储排序后的结果，我们应该使用一种其他的方法，避免数组$nums$中的频繁换位。

针对第一点，我们规定一个归并开始的规模，即当数据规模大于一个数时，才进行归并排序；针对第二点，我们引入一个索引数组$link$，其中$link[i]$表示第$i$个数后面的那个数的下标。

我们可以写出修改后的mergesort和merge，用mergesortL和mergeL表示：

void mergeL(int *lhead, int *rhead, int *head)
{
    int i = *lhead, j = *rhead, k;
    if(nums[i] < nums[j])
    {
        *head = i;
        k = i;
        i = link[i];
    }
    else
    {
        *head = j;
        k = j;
        j = link[j];
    }
    while(i != -1 && j != -1)
    {
        if(nums[i] < nums[j])
        {
            link[k] = i;
            k = i;
            i = link[i];
        }
        else
        {
            link[k] = j;
            k = j;
            j = link[j];
        }
    }
    if(i == -1) link[k] = j;
    else link[k] = i;
}
 
void mergesortL(int start, int end, int *head)
{
    if(end - start + 1 < 5)
    {
        for(int i = start + 1 ; i <= end ; ++i)
        {
            int temp = nums[i];
            int j;
            for(j = i - 1 ; j >= start && nums[j] > temp ; --j)
                nums[j+1] = nums[j];
            nums[j+1] = temp;
        }
        for(int i = start ; i < end ; link[i] = i + 1, ++i);
        link[end] = -1;
        *head = start;
    }
    else
    {
        int mid = start + (end - start) / 2;
        int *lhead = new int(-1);
        int *rhead = new int(-1);
        mergesortL(start, mid, lhead);
        mergesortL(mid+1, end, rhead);
        mergeL(lhead, rhead, head);
    }
}
 
int main()
{
    int *head = new int(-1);
    mergesortL(0, nums.size()-1, head);
    for(int i = *head ; i != -1 ; i = link[i])
        cout << nums[i] << " ";
    cout << endl;
    return 0;
}

使用索引数组之后，元素移动的开销得到了大幅减少，同时规定了最小归并规模(在上文中规定为5)，有效减少了小数组归并带来的出入栈开销。

快速排序

老生常谈了(背板子使人快乐hhh)

void quicksort(vector<int>& nums, int start, int end)
{
    if(start > end) return;
    int pivot = nums[start];
    int i = start, j = end + 1;
    while(true)
    {
        while(nums[++i] < pivot && i < end);
        while(nums[--j] > pivot && j > start);
        if(i < j)
            swap(nums[i], nums[j]);
        else break;
    }
    swap(nums[j], nums[start]);
    quicksort(nums, start, j-1);
    quicksort(nums, j+1, end);
}

顺便用这个分割方法就可以解决第$k$小问题(leetcode传送门)

当然，我们会发现，最坏的情况下(原始数组不增排列)，时间复杂度为$O(n^2)$，对于快排和第$k$小问题，都可以通过精心选择分界元素$pivot$，来降低时间复杂度，这里不做过多的介绍，有兴趣的朋友可以自行查阅资料。

实践 & 结尾

终于到了紧张刺激的coding环节hhh，leetcode中单独有一类分治算法的习题，各位朋友可以拿来练习练习。

水平有限，仓促成文，不当之处，尚祈教正。