详解分治法（divide-and-conquer）及其典型应用

什么是分治法

在昨天的文章《漫谈数据库中的join》的最后，提到Grace hash join和Sort-merge join都是基于分治思想的。分治法（divide-and-conquer）是一种重要的求解复杂问题的算法思想，根据《算法导论》的描述，分治法按照3步执行：

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

也就是说，分治法的“分”是将大问题拆分为子问题，然后再将子问题拆分为更小的子问题，以此类推；“治”则是由小而大递归地解决这些子问题。最后还需要“合”，就是将子问题的解合并，最终得出原问题的解。

分治法的思想非常朴素，是大学计算机系课程中肯定会讲到的内容，但它也是很多精妙算法的基础，比如排序算法中的归并排序和快速排序、计算几何中平面最近点对问题的解法、大整数乘法中的Karatsuba算法与Toom-Cook算法，以及快速傅里叶变换（FFT，也能解决大整数乘法）等。下面选取标为粗体的算法为例来探讨一下。

归并排序

归并排序可以说是分治法最经典的体现：对于一个未排序的有n个元素的序列，不断地将它从中间分开为两个子序列，最终形成n个分别只有1个元素的子序列。只有1个元素的子序列自然是有序的，然后再将它们两两合并起来，并在合并过程中将子序列排序，最终返回的n个元素的合并序列即为有序。其过程如下图所示。

来写个代码实现。大学上数据结构课时都是用C语言来写，这次用Java吧。

public class MyMergeSort implements IMySort {
    private void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            array[left + m] = temp[m];
        }
    }

    @Override
    public void doSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            doSort(array, left, mid);
            doSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

对归并排序而言，设将长度为n的序列排序所需时间为T(n)，那么就存在递归关系：T(n) = 2T(n / 2) + O(n)，进而推导出渐近时间复杂度为：O(n logn)。对于基于分治法的算法，其时间复杂度都可以通过分治法主定理（Master theorem for divide-and-conquer recurrences）来推导。关于该定理，详细的说明可以参见英文维基或者《算法导论》第4章，并不难理解。

快速排序

快速排序也是采用将序列分割的思路来解决问题。以升序排序为例：它先从序列中挑出一个元素，称为“枢轴”或者“基准”（英文pivot），然后将该序列里所有比基准值小的元素都放到基准值前面，所有比基准值大的元素都放到基准值后面，这样就完成了对基准值的排序。然后再按同样的方法，递归地将小于基准值的子序列和大于基准值的子序列排序，直到子序列的长度为0或1（即已经有序）。

同样利用分治法主定理，不难推导出快速排序的渐近时间复杂度也是O(n logn)。

下图示出一个快速排序的过程。

上图中选择基准时，是选择待排序序列的最后一个元素。但是对于已经有序的序列而言，这种选择基准的方法会使复杂度退化到O(n²)。所以一般都选择待排序序列的中间元素作为基准，效率会比较好。代码实现如下：

public class MyQuickSort implements IMySort {
    private void quick(int[] array, int left, int right) {
        if (array.length <= 1 || left >= right) {
            return;
        }

        int i = left, j = right;
        int pivot = array[(i + j) / 2];

        while (i < j) {
            while (array[j] > pivot && i < j) {
                j--;
            }
            if (i < j) {
                array[i++] = array[j];
            }
            while (array[i] < pivot && i < j) {
                i++;
            }
            if (i < j) {
                array[j--] = array[i];
            }
        }
        array[i] = pivot;
        
        quick(array, left, i - 1);
        quick(array, i + 1, right);
    }

    @Override
    public void doSort(int[] array, int left, int right) {
        quick(array, 0, array.length - 1);
    }
}

平面最近点对

最近点对（Closest pair of points）问题即：给出二维平面上的n个点，找出其中距离最近的两个点。显然地，如果暴力求解，时间复杂度为O(n²)，不够高效。然而利用分治法，我们可以巧妙地解决该问题，具体步骤如下：

1. 将点集S中的按x坐标排序；
2. 用一条垂直的直线L将S分为左右均等的两部分，记为S_L和S_R；
3. 递归地计算S_L和S_R中的最近点对距离d_L和d_R；
4. 对于L两侧的点，再计算出跨越L的点对之间的最近距离d_LR；
5. d_L、d_R、d_LR三者的最小值即为解。

上面的解法重点在第4步（当然它与分治的思想本身没什么关系了）。我们已经知道，最近点对的两个点有可能同时在S_L或者S_R中，也有可能分别位于S_L和S_R中。如果记δ=min(d_L, d_R)，那么对于最近点对跨越直线L的情况，其距离也肯定不大于δ。所以，我们以L为中心，左右分别扩展δ的范围，跨越L的最近点对就肯定在这个范围内。

那么我们可以得知，对于S_L内且在虚线范围内的点p，那么最多只有6个S_R内且在虚线范围内的点q能够满足最近点对的条件。这6个点恰好能够形成一个(δ, 2δ)的矩形。利用鸽巢原理可以知道，假设(δ, 2δ)的矩形范围内有7个点与p的距离小于δ，那么这第7个点q'一定也会与矩形的某些顶点距离小于δ，也就破坏了δ=min(d_L, d_R)的条件。因此，最多尝试6次就可以找到d_LR了。

经由上面的分析，我们就可以知道该解法仍然存在T(n) = 2T(n / 2) + O(n)的关系，也就是说仍然能在O(n logn)时间内解决。这里就不再写代码，有两道题目可以供练手用，分别是HDOJ 1007与POJ 3714。

大数乘法的Karatsuba算法

所谓大数乘法，就是指超出计算机中基本数据类型范围的乘法运算，不能直接进行。该问题的暴力求解方法就是用程序模拟竖式乘法，时间复杂度是O(n²)。然而，苏联数学家Anatoly Karatsuba在上世纪60年代提出了一个基于分治思想的大数乘法算法，可以将复杂度改善到O(n^log3)。其详细描述仍然可以参考英文维基，下面简单地描述一下Karatsuba算法。

令x和y是两个要做乘法的十进制大数，并且位数都为n，那么x、y可以表示成：

x = a · 10^n/2 + b, y = c · 10^n/2 + d

也就是说，将x和y分别切成两部分，每部分有n/2位。那么就有：

x · y = (a · 10^n/2 + b)(c · 10^n/2 + d)

再进一步：

x · y = ac · 10ⁿ + (ad + bc) · 10^n/2 + bd

其中又产生了ac、ad、bc、bd四个乘法运算。其中，计算(ad + bc)需要做两次乘法，但是容易得知：

(a+c)(b+d) - ac - bd = ad + bc

所以可以简化为3个乘法运算，毕竟减法比乘法要简单得多。如果这些乘法仍然属于大数乘法的范畴，就分别再切分并递归下去，直到子问题变成小整数的乘法为止。很显然，该算法也可以扩展到非10进制的计算上去。

下图用一个简单的1234 × 567展示出了Karatsuba算法的过程。

Karatsuba算法的实现就在我们身边，准确来说，是在JDK 8+的大整数类java.math.BigInteger的multiplyKaratsuba()方法里，其代码如下。

    private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) {
        int xlen = x.mag.length;
        int ylen = y.mag.length;

        // The number of ints in each half of the number.
        int half = (Math.max(xlen, ylen)+1) / 2;

        // xl and yl are the lower halves of x and y respectively,
        // xh and yh are the upper halves.
        BigInteger xl = x.getLower(half);
        BigInteger xh = x.getUpper(half);
        BigInteger yl = y.getLower(half);
        BigInteger yh = y.getUpper(half);

        BigInteger p1 = xh.multiply(yh);  // p1 = xh*yh
        BigInteger p2 = xl.multiply(yl);  // p2 = xl*yl

        // p3=(xh+xl)*(yh+yl)
        BigInteger p3 = xh.add(xl).multiply(yh.add(yl));

        // result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
        BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);

        if (x.signum != y.signum) {
            return result.negate();
        } else {
            return result;
        }
    }

值得一提的是，JDK会根据两个乘数的大小选择不同的算法。当小于(2³²)⁸⁰时，会用暴力算法相乘；大于(2³²)⁸⁰而小于(2³²)²⁴⁰时，就用上述Karatsuba算法相乘；大于(2³²)²⁴⁰时，就用更先进的Toom-Cook算法相乘。Toom-Cook算法也是基于分治的，但是它更加复杂，并且本文已经很长了，还是就此打住吧。

晚安。