分治的思维方式

算法，其本质是一种思维方式。具体实现是术，思维方式是道。对于分治算法，它对应的数学理论是数学归纳法。在程序的表现中，它一般会和递归一起使用。

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

这是维基百科对分治法的定义。分治法的核心思想如下：

找到一个(或多个，下同)比现有问题规模更小的，但本质却一样的问题
找到问题的基准值（也就是最小的，不可以再切割的那个条件）
把问题依次化解为更小的问题，一直到基准值为止
当基准值被解决之后，递归函数一路向上返回
合并递归函数返回的结果

比如在Haskell中，列表求和函数可以如下实现：

mySum :: [Int] -> Int  -- 函数签名
mySum [] = 0  -- 基准情况，空列表，不能再切分为子问题了
mySum (x:xs) = x + mySum xs  -- 分治

我们可以把一个列表看作是一个元素和一个列表拼在一起，比如有一个列表为 [1, 2, 3]，我们可以看成是 1 和 [2, 3] 拼在一起，我们发现，这样可以把列表求和的问题分成一个相似的子问题，那就是1和 [2, 3] 的和，同理，[2, 3] 还可以继续细分为 2 和 [3] 的和，而 [3] 可以分为 3 和 [] 的和，那么 [] 就是基准情况，空列表的和是多少呢？显然是0，因此我们开始把展开的递归层层向上收缩，得出最终的结果为6。

那有可能有人想问，为啥要这样做呢？为啥不直接迭代过去累加呢？这是两种不同的思维方式，关于分治，我们再来看很熟悉的一个排序算法：合并排序。

合并排序

使用Python实现合并排序如下：

def merge(array):
    if len(array) == 1:
        return array

    mid = len(array) >> 1
    left = merge(array[:mid])
    right = merge(array[mid:])
    result = []
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] > right[j]:
            result.append(right[j])
            j += 1
        else:
            result.append(left[i])
            i += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

同样，基准情况是当数组只有一个值的时候，这个时候原样返回；而当数组内有多个值的时候，把数组一分为二，递归处理，然后将递归的返回值进行合并，合并方法是，将左右两边同时遍历，每次都选择最小的那个；最后将没有遍历完的那一部分拼上去。

那么为什么可以把递归的返回值直接进行合并呢？这里就涉及到分治算法一个比较难理解的地方，突破了这一点，也就掌握了分治算法。那就是递归信任。也就是我们的目标是，将左右半部分排序的操作分别放到递归函数里去做，当递归函数返回的时候，他们必然是有序的，为什么呢？因为所有的递归函数都执行了合并的那一部分操作。可能有些绕，但是仔细去理解一下，就会发现不难。

我们继续扩展，除了合并排序，还有什么地方是可以用分治法去解决的呢？

把大批量的数据分为n次执行

日常业务实现中，也有分治法的影子。比如，在一个数据库查询中，使用IN操作，而IN后面接了10240个值，这个时候如果直接丢到SQL 里查询，那必然是要出问题的，我们可以分为10个批次，每批次1024个值去查询，然后把他们的结果进行合并处理。

这个场景是不是很熟悉呢？再比如，线程池，进程池处理多任务的时候，如果一次发起1024个线程执行任务，那系统可能会吃不消，这个时候我们会选择一个合适大小的线程池，让他们慢慢执行，最后我们再统一处理结果(或者忽略结果)，这样的例子很多，比如 Python中的ThreadPoolExecutor，Go里的 sync.WaitGroup，Java的线程池等等。

递归的数据结构和问题

还有什么数据结构我们可以用递归的方式(因此也就可以用分治来解决)来看待呢？

树
链表
汉诺塔问题

这些我们都可以把它们拆城一个值和一个相同性质的子问题来看待，因此也就可以使用分治的思维方式去解决他们。

参考资料：

分治的思维方式

合并排序

把大批量的数据分为n次执行

递归的数据结构和问题

更多文章