第1-3课：算法设计常用思想之分治法

悠悠 2022-12-09 11:38 158阅读 0赞

> 在第 1-2 课中介绍了算法模式中的贪婪法，这一课我们继续介绍分治法。分治，顾名思义，分而治之。分治法（Divide and Conquer）也是一种解决问题的常用模式，分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题，然后逐个解决小问题，即所谓分而治之。分治法产生的子问题与原始问题相同，只是规模减小，反复使用分治方法，可以使得子问题的规模不断减小，直到能够被直接求解为止。

### 分治法的基本思想 ###

分治法作为算法设计中一个古老的策略，在很多问题中得到了广泛的应用，比如最轻、最重问题（在一堆形状相同的物品中找出最重或最轻的那一个），矩阵乘法、大整数乘法以及排序（例如，快速排序和归并排序）。除此之外，这个技巧也是许多高效算法的基础，比如快速傅立叶变换算法和 Karatsuba 乘法算法。

应用分治法，一般出于两个目的，其一是通过分解问题，使得无法着手解决的大问题变成容易解决的小问题，其二是通过减小问题的规模，降低解决问题的复杂度（或计算量）。给 1000 个数排序，可能会因为问题的规模太大而无从下手，但是如果减小这个问题的规模，将问题一分为二，变成分别对两个拥有 500 个数的序列排序，然后再将两个排序后的序列合并成一个就得到了 1000 个数的排序结果。对 500 个数排序仍然无法下手，需要继续分解，直到最后问题的规模变成 2 个数排序的时候，只需要一次比较就可以确定顺序。这正是快速排序的实现思想，通过减小问题的规模使问题由难以解决变得容易解决。计算 N 个采样点的离散傅立叶变换，需要做 N2 次复数乘法，但是将其分解成两个 N/2 个采样点的离散傅立叶变换，则只需要做 (N/2)2 \+(N/2)2 = N2/2 次复数乘法，做一次分解就使得计算量减少了一半，这正是快速傅立叶变换（FFT）的实现思想，通过减小问题的规模来减少计算量，以降低问题的复杂度。

在很多情况下，分治法都会使用递归的方式对问题逐级分解，但是在每个子问题的层面上，分治法基本上可以归纳为三个步骤：

*  **分解：**将问题分解为若干个规模较小，相互独立且与原问题形式相同的子问题，确保各个子问题的解具有相同的子结构；
 *  **解决：**如果上一步分解得到的子问题可以解决，则解决这些子问题，否则，对每个子问题使用和上一步相同的方法再次分解，然后求解分解后的子问题，这个过程可能是一个递归的过程；
 *  **合并：**将上一步解决的各个子问题的解通过某种规则合并起来，得到原问题的解。

分治法的实现模式可以是递归方式，也可以是非递归方式，一般采用递归方式的算法模式可以用伪代码描述为：

T DivideAndConquer(P)
    {
        if(P可以直接解决)
        {
            T <- P的结果;
            return T;
        }
    
        将P分解为子问题{P1, P2,..., Pn};
        for_each(Pi : {P1, P2,..., Pn})
        {
            ti <- DivideAndConquer(Pi); //递归解决子问题Pi
        }
        T <- Merge(t1, t2,...,tn); //合并子问题的解
    
        return T;
    }

分治法的难点是如何将子问题分解，并且将子问题的解合并出原始问题的解，针对不同的问题，通常有不同的分解与合并的方式。先来看看快速排序算法，快速排序算法的分解思想是选择一个标兵数，将待排序的序列分成两个子序列，其中一个子序列中的数都小于标兵数，另一个子序列中的数都大于标兵数，然后分别对这两个子序列排序，其合并思想就是将两个已经排序的子序列一前一后拼接在标兵数前后，组成一个完整的有序序列。再来看看快速傅立叶变换，快速傅立叶变换的分解思想是将一个 N 点离散傅立叶变换，按照奇偶关系分成两个 N/2 点离散傅立叶变换，其合并思想就是将两个 N/2 点离散傅立叶变换结果按照蝶形运算的位置关系重新排列成一个 N 点序列。最后再介绍一下 Karatsuba 乘法算法，Karatsuba 算法的分解思想是将 n 位大数分成两部分：a + b，其中 a 是整数幂，然后利用乘法的分解公式：(a+b)(c+d) = ac + ad + bc + bd，将其分解为四次小规模大数的乘法计算，然后利用一个小技巧将其化解成三次乘法和少量移位操作，最终结果的合并思想就是用几次加法对小规模乘法的结果进行求和，得到原始问题的解。

由以上的例子可知，分治法最难，也是最灵活的部分就是对问题的分解和结果的合并，对于一个未知的问题，只要能找到对子问题的分解方式和结果的合并方式，应用分治法就可以迎刃而解。而在数学上，只要能用数学归纳法证明的问题，一般也都可以应用分治法解决，这也是一个应用分治法的强烈信号。

### 递归和分治，一对好朋友 ###

递归作为一种算法的实现方式，与分治法是一对儿天然的好朋友。问题的分解肯定不是一步到位，需要反复使用分治手段，在多个层次上层层分解，这种分解的方法很自然地导致了递归方式的使用。从算法实现的角度看，分治法得到的子问题和原问题是相同的，当然可以用相同的函数来解决，区别只在于问题的规模和范围不同。通过特定的函数参数安排，使得同一个函数可以解决不同规模的相同问题，这就是递归方法的基础。

以快速排序为例，如果把待排序的序列作为问题的话，那么子问题的规模就可以定义为子序列在原始序列中的起始位置。对此一般化之后，原始问题和子问题的描述就统一了，都是原始序列 + 起始位置，原始问题的起始位置就是 \[1,n\]，子问题的起始位置就是 \[1,n\] 中的某一个子区间，由此一来，递归的接口就明确了：

void quick_sort(int *arElem, int p, int r)

其中，p 和 r 就分别是子序列在 arElem 中的起始位置，有了子问题的递归定义接口，快速排序的算法实现也就水到渠成了：

void quick_sort(int *arElem, int p, int r)
    {
      if(p < r)
      {
        int mid = partion(arElem, p, r);
        quick_sort(arElem, p, mid - 1);
        quick_sort(arElem, mid + 1, r);
      }
    }

不用递归是不是就不能用分治法了？当然不是，快速傅立叶变换算法就没有用递归。很多算法都有自己的非递归实现方式，是不是用了递归方法不是判断是否是分治法的必要条件。即便是一些使用了递归方法的算法，也都可以用一个自己构造的栈将其改编为非递归方法，比如快速排序就有很多用栈实现的非递归方法。Robert Sedgewick 在其著作《Algorithm in C》一书中就给出了一种快速排序的非递归高效算法，有兴趣的读者可阅读此书，了解一下算法实现。

### 分治法的例子：大整数 Karatsuba 乘法算法 ###

两个 n 位大整数相乘，普通乘法算法的时间复杂度一般是 O(n2)，但是 Anatolii Alexeevitch Karatsuba 博士在 1960 年提出了一种时间复杂度是 O(3n1.585)(1.585 = log23) 的快速乘法算法，这就是 Karatsuba 乘法算法。Karatsuba 算法就是利用了分治法的思想，将 n 位大整数分解成两个接近 n/2 位的大整数，通过 3 次 n/2 位大整数的乘法和少量加法操作，避免了直接进行 n 位大整数乘法计算，有效地降低了乘法计算的计算量。

Karatsuba 算法的原理非常简单，假如有两个 n 位的 M 进制大整数 x，y，利用一个小于 n 的正数 k（通常 k 取值为 n/2 左右），将 x 和 y 分解为两部分：

![gif.latex?&space;x&space;=&space;x\_\{1\}M^\{k\}&space;&plus;&space;x\_\{0\}][gif.latex_space_x_space_space_x_1_M_k_space_plus_space_x_0]

![gif.latex?&space;y&space;=&space;y\_\{1\}M^\{k\}&space;&plus;&space;y\_\{0\}][gif.latex_space_y_space_space_y_1_M_k_space_plus_space_y_0]

则 x 和 y 的乘积可计算为：

![gif.latex?xy&space;=&space;(x\_\{1\}M^\{k\}&space;&plus;&space;x\_\{0\})(y\_\{1\}M^\{k\}&space;&plus;&space;y\_\{0\})&space;=&space;x\_\{1\}y\_\{1\}M^\{2k\}&space;&plus;&space;(x\_\{1\}y\_\{0\}&space;&plus;&space;x\_\{01\}y\_\{1\})M^\{k\}&space;&plus;&space;x\_\{0\}y\_\{0\}][gif.latex_xy_space_space_x_1_M_k_space_plus_space_x_0_y_1_M_k_space_plus_space_y_0_space_space_x_1_y_1_M_2k_space_plus_space_x_1_y_0_space_plus_space_x_01_y_1_M_k_space_plus_space_x_0_y_0]

这样就将 x 和 y 的乘法计算转化成四次较小规模的乘法计算和少量加法计算，其中 M2k 和 Mk 的计算都可以通过移位高效地处理。不过上述操作还可以继续优化，我们令

![gif.latex?\\inline&space;z\_\{0\}=x\_\{0\}y\_\{0\}][gif.latex_inline_space_z_0_x_0_y_0]

![gif.latex?\\inline&space;z\_\{1\}=x\_\{1\}y\_\{0\}&space;&plus;&space;x\_\{0\}y\_\{1\}][gif.latex_inline_space_z_1_x_1_y_0_space_plus_space_x_0_y_1]

![gif.latex?\\inline&space;z\_\{2\}=&space;x\_\{1\}y\_\{1\}][gif.latex_inline_space_z_2_space_x_1_y_1]

则 xy 的乘积可表示为：

![gif.latex?xy&space;=&space;z\_\{2\}M^\{2k\}&space;&plus;&space;z\_\{1\}M^\{k\}&space;&plus;&space;z\_\{0\}][gif.latex_xy_space_space_z_2_M_2k_space_plus_space_z_1_M_k_space_plus_space_z_0]

计算 z1 需要两次乘法，对 z1 的计算可以优化为：

![gif.latex?z\_\{1\}&space;=&space;(x\_\{1\}&space;&plus;&space;x\_\{0\})(y\_\{1\}&space;&plus;&space;y\_\{0\})&space;-&space;x\_\{1\}y\_\{1\}&space;-&space;x\_\{0\}y\_\{0\}&space;=&space;(x\_\{1\}&space;&plus;&space;x\_\{0\})(y\_\{1\}&space;&plus;&space;y\_\{0\})&space;-&space;z\_\{2\}&space;-&space;z\_\{0\}][gif.latex_z_1_space_space_x_1_space_plus_space_x_0_y_1_space_plus_space_y_0_space_-_space_x_1_y_1_space_-_space_x_0_y_0_space_space_x_1_space_plus_space_x_0_y_1_space_plus_space_y_0_space_-_space_z_2_space_-_space_z_0]

由于 z0 和 z2 都已经计算过了，因此就只需一次乘法，辅助两次加法和两次减法即可计算出 z1。

Karatsuba 算法的主要原理就是将两个大整数乘法运算分解成四个小整数的乘法和加减法组合运算。第一步是分解问题，将参与乘法运算的两个大整数分解为四个小整数；第二步是求解小整数之间的乘法运算，需要三次小整数的乘法运算和若干次加减、移位运算；第三步是按照公式将这些运算的结果组合成大整数运算的结果。其中第二步中每一次小整数的乘法运算可以理解为是再次利用 Karatsuba 算法的原理继续分解为四个更小的整数进行运算。显然，用递归的方法设计这个算法是最自然的方式，递归的终止条件就是参与乘法运算的两个大整数之一无法再分解为更小的整数为止（即只有一个 M 进制大整数位），此时两个大整数可以直接用乘法计算出结果。为了演示算法，我们假设 CBigInt 类是一个 n 位的 232 进制大数，可以理解为 M=232，利用 CBigInt 类的实现，我们给出 n 位的 232 进制大数的 Karatsuba 乘法算法实现（大家可以从[图灵社区的网站下载《算法的乐趣》一书的源代码][Link 1]，里面有 CBigInt 类的实现）：

CBigInt Karatsuba(const CBigInt& mul1, const CBigInt& mul2)
    {
        //1位大整数，直接计算，这也是递归的终止条件
        if((mul1.GetBigNCount() == 1) || (mul2.GetBigNCount() == 1))
        {
            return mul1 * mul2;
        }
        //问题分解
        CBigInt high1,high2,low1,low2;
        unsigned int k = max(mul1.GetBigNCount(), mul2.GetBigNCount()) / 2;
        high1 = mul1;
        high1.GetRightBigN(k, low1);
        high1.ShiftRightBigN(k);
        high2 = mul2;
        high2.GetRightBigN(k, low2);
        high2.ShiftRightBigN(k);
        CBigInt z0 = Karatsuba(low1, low2);
        CBigInt zk = Karatsuba((low1 + high1), (low2 + high2));
        CBigInt z2 = Karatsuba(high1, high2);
        //结果合并
        CBigInt z1 = zk - z2 - z0;
        z2.ShiftLeftBigN(2 * k);
        z1.ShiftLeftBigN(k);
    
        return (z2 + z1 + z0);
    }

[gif.latex_space_x_space_space_x_1_M_k_space_plus_space_x_0]: /images/20221123/8d6eee5fc7924c6daac38188970ecbed.png
[gif.latex_space_y_space_space_y_1_M_k_space_plus_space_y_0]: /images/20221123/71e4042cc7ce48318146d03763c1e8ff.png
[gif.latex_xy_space_space_x_1_M_k_space_plus_space_x_0_y_1_M_k_space_plus_space_y_0_space_space_x_1_y_1_M_2k_space_plus_space_x_1_y_0_space_plus_space_x_01_y_1_M_k_space_plus_space_x_0_y_0]: /images/20221123/5f159187f8404421b45578b6da54fd83.png
[gif.latex_inline_space_z_0_x_0_y_0]: /images/20221123/3364e3c03cff46078f5ddbf9b7fcce16.png
[gif.latex_inline_space_z_1_x_1_y_0_space_plus_space_x_0_y_1]: /images/20221123/e74ad81ee4824d99969e41693801fee7.png
[gif.latex_inline_space_z_2_space_x_1_y_1]: /images/20221123/5fc20cce826f4557bf08052bf9ff0eb8.png
[gif.latex_xy_space_space_z_2_M_2k_space_plus_space_z_1_M_k_space_plus_space_z_0]: /images/20221123/293611c0cc924927945a61ee8bfd5b71.png
[gif.latex_z_1_space_space_x_1_space_plus_space_x_0_y_1_space_plus_space_y_0_space_-_space_x_1_y_1_space_-_space_x_0_y_0_space_space_x_1_space_plus_space_x_0_y_1_space_plus_space_y_0_space_-_space_z_2_space_-_space_z_0]: /images/20221123/1b43402014244bf398935089b69280dc.png
[Link 1]: http://www.ituring.com.cn/book/1605