分治算法的设计与分析-归并排序

摘要: 以归并排序为例来看分治算法的设计与分析

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

分治法的设计思路

一些算法在结构上是递归的，为了解决一个给定的问题，算法一次或多次递归地调用自身以解决相关的若干子问题。分治就是这样的算法，将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立新问题的解。

分治法在每层递归中有以下三个步骤：

• 分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
• 解决：递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解
• 合并：将子问题的解组合成原问题的解

设计分治算法例子：归并排序

归并排序算法遵循分治的模式：

• 分解：待排序的 n 个元素分解为各有 $\frac{n}{2}$ 的两个子序列
• 解决：递归地排序两个子序列
• 合并：合并两个已经排序的子序列，产生完整序列的排序结果

待排序的序列长度为 1 时，则问题已解决，因为长为 1 的序列已排好序。因此对分治算法来说，解决是比较简单的，关键操作是合并。

合并步骤，做的是把两个已排序的序列进行合并。考虑数组 A 的两个子数组 A[p..q], A[q+1..r] 都已经排好序，满足 $p \leq q < r$，合并好后，得到已排好序的子数组 A[p..r]。

两个子数组共有 r - p + 1 个数，开一个新的长为 r - p + 1 的数组，保存合并结果。然后执行一个选数过程，每一轮分别考察两个子数组的左端数字，取出较小的那个，插入到新数组的尾部，执行 r - p + 1 轮后，新数组中就是合并后从小到大排好序的数组。

这个合并过程有相应的题目可以参考，一个数组的，一个链表的，分别对应数组归并排序和链表归并排序的合并过程。88. 合并两个有序数组；21. 合并两个有序链表。

代码：合并过程 (C++)

// 非常经典的归并操作
// 类似问题例如链表的二路归并，多路归并等
void _merge(vector<int>& nums, int low, int mid, int high)
{
    // 归并时候的辅助数组
    vector<int> tmp(high - low + 1, 0);
    // 下面这么写的话，往辅助数组里插入需要 push_back
    // static vector<int> tmp;
    // tmp.clear();

    int i = low, j = mid, k = 0;
    while(i < mid && j <= high)
    {
        if(nums[i] < nums[j])
        {
            tmp[k] = nums[i];
            ++k;
            ++i;
        }
        else
        {
            tmp[k] = nums[j];
            ++k;
            ++j;
        }
    }
    while(i < mid) tmp[k++] = nums[i++];
    while(j <= high) tmp[k++] = nums[j++];
    for(k = 0, i = low; i <= high; ++k, ++i)
        nums[i] = tmp[k];
}

代码：分治算法框架 (C++)

分治算法框架：分解-解决-合并。

一般通过递归的方式实现分解-解决-合并的算法框架。

// 自顶向下
void _mergesort_topdown(vector<int>& nums, int low, int high)
{
    int mid = low + (high - low) / 2;
    if(low == high) 
        return;
    _mergesort_topdown(nums, low, mid);
    _mergesort_topdown(nums, mid + 1, high);
    _merge(nums, low, mid + 1, high); // 归并左右两个有序表
}

对于数组归并排序，每次都是从中点处分解，因此每一轮合并的下标范围可以实现算出来，这样可以将递归改为直接通过下标的方式，自底向上地实现。

// 自顶向下
void _mergesort_topdown(vector<int>& nums, int low, int high)
{
    int mid = low + (high - low) / 2;
    if(low == high) return;
    _mergesort_topdown(nums, low, mid);
    _mergesort_topdown(nums, mid + 1, high);
    _merge(nums, low, mid + 1, high); // 归并左右两个有序表
}

代码：数组归并排序 (C++)

// 归并, 自顶向下
void mergesort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    _mergesort_topdown(nums, 0, n - 1);
}

---

分治法的分析思路

当一个算法包含地柜的时候，往往可以用递归式描述运行时间。递归式是一个等式或不等式，通过更小的输入上的函数值来描述一个函数(运行时间)。

分治法的递归式来自分治的算法框架的三个步骤，设 $T(n)$ 为规模为 n 的问题的运行时间，分析过程如下：

• 若问题规模足够小，比如 $n < c$，时间为 $\Theta(1)$。
• 假设把原问题分解为 $a$ 个子问题，每个子问题的规模是原问题的 $\frac{1}{b}$。
• 假设分解的过程需要 $D(n)$ 的时间。
• 假设合并的过程需要 $C(n)$ 的时间。

那么就可以得到递归式：

$$T(n) = \left\{ \begin{array}{**lr**} \begin{align} &\Theta(1) & n \leq c \\ &aT(\frac{n}{b}) + D(n) + C(n) & other \\ \end{align} \end{array} \right.$$

上面的递归式中参数很多，根据实际算法，递归式可以有很多形式。比如

• 子问题划分不是对半，而是 1/3，2/3，分解和合并都是线性的，那么有 $T(n) = T(n/3) + T(2n/3) + \Theta(n)$；
• 子问题只有一个，且规模不是 n 的比例，而是少一个元素，也就是 n - 1，则 $T(n) = T(n - 1) + \Theta(1)$。这种划分子问题后，只处理其中一个子问题的算法也称为减治法。

有时递归式是不等式，例如 $T(n) \leq 2T(\frac{n}{2}) + \Theta(n)$，这样的递归式进描述了 $T(n)$ 的一个上界，因此可以用 $O$ 符号描述其解。类似地 $T(n) \geq 2T(\frac{n}{2}) + \Theta(n)$，可以用 $\Omega$ 符号描述。

分析分治算法例子：归并排序

下面分析归并排序 n 个数的最坏情况运行时间 $T(n)$ 的递归式。

• 归并排序一个元素需要常量时间 $\Theta(1)$
• 分解：仅计算子数组的中间位置，需要常量时间 $D(n) = \Theta(1)$
• 解决：递归地求解两个规模为 $\frac{n}{2}$ 的子问题，运行时间为 $2T(\frac{n}{2})$
• 合并：在一个具有 n 个元素的子数组上，合并过程需要 $\Theta(n)$ 的时间，因此 $C(n) = \Theta(n)$

由此得到 $T(n)$ 的递归式：

$$T(n) = \left\{ \begin{array}{**lr**} \begin{align} &\Theta(1) & n = 1 \\ &2T(\frac{n}{2}) + \Theta(n) & n > 1 \\ \end{align} \end{array} \right.$$

---

递归式的求解

写出分治法运行时间 $T(n)$ 的递归式后，求解这个递归式主流有以下三种方法：

• 代入法：猜测一个界，然后用数学归纳法证明这个界是正确的。
• 递归树法：将递归式转换为一棵树，其节点表示不同层次的递归调用产生的代价，采用边界和技术求解递归式。
• 主方法：可以求解形如 $T(n) = aT(n/b) + f(n)$ 其中 $a\geq 1, b > 1$ 形式的递归式的界。这个形式的递归式刻画了这样的分治算法：生成 $a$ 个子问题，每个子问题规模是原问题的 $\frac{1}{b}$，分解和合并共花费时间 $f(n)$。

主方法

主方法依赖于下面的主定理：

主定理

令 $a \geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是定义在非负整数上的递归式：

$$T(n) = aT(\frac{n}{b}) + f(n)$$

其中我们将 $\frac{n}{b}$ 解释为 $\lfloor\frac{n}{b}\rfloor$ 或 $\lceil\frac{n}{b}\rceil$，那么 $T(n)$ 有如下渐进界：
(1) 若对某个常数 $\epsilon > 0$ 有 $f(n) = O(n^{\log_{b}a-\epsilon})$，则 $T(n) = \Theta(n^{\log_{b}a})$；
(2) 若 $f(n) = \Theta(n^{\log_{b}a})$，则 $T(n) = \Theta(n^{\log_{b}a}\log n)$；
(3) 若对某个常数 $\epsilon > 0$ 有 $f(n) = \Omega(n^{\log_{b}a-\epsilon})$，且对某个常数 $c < 1$ 和足够大的 $n$ 有 $af(\frac{n}{b}) \leq cf(n)$，则 $T(n) = \Theta(f(n))$。

三种情况的每一种，我们将函数 $f(n)$ 与 $n^{\log_{b}a}$ 比较（多项式意义的渐进大于、小于、等于）：

• 若 $n^{\log_{b}a}$ 更大，则为情况 (1)，解为 $T(n) = \Theta(n^{\log_{b}a})$；
• 若 $f(n)$ 更大，则为情况 (3)，解为 $T(n) = \Theta(f(n))$；
• 若大小相当，则为情况 (2)，乘上一个对数因子，解为 $T(n) = \Theta(n^{\log_{b}a}\log n) = \Theta(f(n)\log n)$。

注意这三种情况没有覆盖 $f(n)$ 的所有可能性，不满足三种情况之一的递归式不能用主方法来求解。

用主方法求解递归式，只需要确定主定理的哪种情况成立，即可得到解。

对于归并排序的 $T(n) = 2T(\frac{n}{2}) + \Theta(n)$，由主方法可以得到 $\Theta(n\log n)$。

递归树

归并排序的分治算法的 $T(n)$ 的递归式如下：

$$T(n) = \left\{ \begin{array}{**lr**} \begin{align} &c & n = 1 \\ &2T(\frac{n}{2}) + cn & n > 1 \\ \end{align} \end{array} \right.$$

其中常量 $c$ 代表求解规模为 1 的问题所需的时间以及在分解与合并过程中处理每个数组元素所需时间（$\Theta(1)$）。

下面的分析为了方便假设 $n$ 为 2 的幂。

如图 (a) 表示 $T(n)$，它在 (b) 被扩展为一棵描述递归式的树，$cn$ 为树根，表示递归的顶层引起的代价，两棵子树是是两个较小的递归式 $T(\frac{n}{2})$，图 (c) 表示 $T(\frac{n}{2})$ 进一步扩展的过程。

重复扩展直至问题规模下降到 1，此时每个子问题的时间为 $c$，如图 (d)。

接着将这棵树的每层的所有代价相加，顶层总代价 $cn$，下一层 $c\frac{n}{2} + c\frac{n}{2} = cn$，第 $i$ 层有 $2^{i}$ 个节点，每个节点贡献代价 $c\frac{n}{2^{i}}$，因此第 $i$ 层总代价为 $2^{i}c\frac{n}{2^{i}} = cn$。

为了计算递归式的总代价，只需要把各层的代价加起来，递归树的层数为 $\log n + 1$ 其中 n 是叶子数，每层代价为 $cn$，所以总代价为 $cn(\log n + 1)$，也就是 $\Theta(n\log n)$。

---