开源一夏 | 分治算法其实很有趣

生活中的递归与分治

“你站在桥上看风景，看风景的人在楼上看你，明月装饰了你的窗子，你装饰了别人的梦。”——卞之琳《断章》

上面这首诗包含了一个递归的概念。生活中无处不是递归~

递归又常常与算法里面且难以避免的另一个重要概念“分治”（分而治之）紧密联系。事实上，递归在很多时候就是因为分治策略的使用才出现的，可以说没有递归，就没有分治。

分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关，但它的确是当之无愧：因为很多有效的算法实际上就是这个通用算法的特殊实现。

分而治之是一个非常重要的战略：

• 战国时期纵横之术就使得秦国通过合纵连横的分治策略而统一了当时的六国（具体措施：笼络燕齐，稳住魏楚，消灭韩赵；远交近攻，逐个击破。）秦国，就是在与六国连横的过程中，一方面击破了合纵，另一方面不断深挖本国的潜能，使国家不断的富强，最终取得了统一霸业的伟大胜利。

• 在 LPL 游戏比赛中，为了选出最强的的四支队伍去参加世界赛，所有的队伍都进行对抗会使得赛程太久，成本很高。所以通过分治的策略：首先将不同的战队分为上下半区，从每个半区通过 BO5 淘汰赛来选出最优秀的战队。又加入了胜者组合败者组的复活赛，最后通过决赛角逐出一直最顶尖的队伍成为世界赛 1 号种子。

说完上面这些之后，我们来看看正式一点的概念。

分治算法概念与步骤

定义：分治算法（Divide and Conquer）：字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

算法步骤：

1. 分解：将一个问题划分为同一类型的若干个子问题，子问题最好规模相同

2. 求解：对这些子问题求解（一般使用递归方法，但在问题规模足够小时，也会使用其他算法）

3. 合并：如果还需要，合并子问题的解，以得到原始问题的答案

用图来表示的话，如下

其中，第二步递归解决子问题就是按照同样的分治策略进行求解，通过将这些子问题分解为更小的孙子问题进行求解。直到分解出来的子问题简单到只用常数操作时间即可解决为止。

其对应的伪代码如下：

def divide_and_conquer(problem):                # problem 为问题规模    if problem < d:                             # 当问题规模足够小时，直接解决该问题        return solove();                        # 直接求解        k_problems = divide(problem)                # 将问题分解为 k 个相同形式的子问题        res = [0 for _ in range(k)]                 # res 用来保存 k 个子问题的解    for k_problem in k_problems:        res[i] = divide_and_conquer(k_problem)  # 递归的求解 k 个子问题        ans = merge(res)                            # 合并 k 个子问题的解    return ans                                  # 返回原问题的解

分治算法的适用条件

分治算法能够解决的问题，一般需要满足以下 4 个条件：

1. 原问题可以分解为若干个规模较小的相同子问题。

2. 分解出来的子问题可以独立求解，即子问题之间不包含公共的子子问题。

3. 具有分解的终止条件，也就是说当问题的规模足够小时，能够用较简单的方法解决。

4. 子问题的解可以合并为原问题的解，并且合并操作的复杂度不能太高，否则就无法起到减少算法总体复杂度的效果了。

分治算法的应用

归并排序

归并排序是成功应用分治策略的一个完美例子，对于给定一组序列含 n 个数组 A[0..n-1]，归并排序将其一分为二：A[0..⌊n/2⌋-1] 和 A[⌊n/2⌋..⌊n-1⌋]，并对每个子数组递归排序，然后将这两个排好序的子数组合并为一个有序数组。

Go 代码如下：

func mergeSort(items []int) []int {    if len(items) < 2 {        return items    }    first := mergeSort(items[:len(items)/2])    second := mergeSort(items[len(items)/2:])    return merge(first, second)}

让我们先编写 mergeSort() 函数。它是一个递归函数，这意味着它会调用自己，在这种情况下，它实际上会调用自己两次。 mergeSort 函数的要点是将数组分成大致相等的两个部分，在这些部分上调用自身，然后调用 merge() 将这些部分重新组合在一起。

merge() 函数用于将两个排序列表合并回一个排序列表，这是真正发生“魔术”的地方。在递归的最低级别，两个“排序”列表的长度均为 1。这些单元素列表将合并为长度为 2 的排序列表，我们可以从那里构建。然后写出归并的 merge() 函数：

func merge(a []int, b []int) []int {    final := []int{}    i := 0    j := 0    for i < len(a) && j < len(b) {        if a[i] < b[j] {            final = append(final, a[i])            i++        } else {            final = append(final, b[j])            j++        }    }    for ; i < len(a); i++ {        final = append(final, a[i])    }    for ; j < len(b); j++ {        final = append(final, b[j])    }    return final}

然后在 main() 函数中验证：

func main() {	unsorted := []int{8, 3, 2, 9, 7, 1, 5, 4}	sorted := mergeSort(unsorted)
	fmt.Println(sorted)
	// sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9]}

二分查找

目的：在一个含有 N 个元素的有序数组中有效地的定位目标值。

​思想​：假设在有序数组 arr 中查找元素 k，返回 k 所在的下标（索引值）。设​​ arr[low,high]​​ 是当前的查找区间，确定该区间的中间位置 mid=⌊(low+high)//2⌋ ，然后将待查的 k 值与 arr[mid] 比较:

• 若​​k==arr[mid]​​，说明找到 k，则查找成功并且终止，则找到该元素；

• 若​​k<arr[mid]​​，根据数组有序的前提，目标值 k 在左边的区域中，索引的范围改为 [low, mid-1]
  

• 若​​k>arr[mid]​​，目标值在右边的区域中，查找索引范围改为 [mid+1, high]
  

示例：

输入    nums = [-1,0,3,5,9,12], target = 9输出    4解释    9 出现在 nums 中并且下标为 4

Python 代码如下：

class Solution:    def search(self, nums: List[int], target: int) -> int:        left = 0        right = len(nums) - 1        # 在区间 [left, right] 内查找 target        while left < right:            # 取区间中间节点            mid = left + (right - left) // 2            # nums[mid] 小于目标值，排除掉不可能区间 [left, mid]，在 [mid + 1, right] 中继续搜索            if nums[mid] < target:                left = mid + 1             # nums[mid] 大于等于目标值，目标元素可能在 [left, mid] 中，在 [left, mid] 中继续搜索            else:                right = mid        # 判断区间剩余元素是否为目标元素，不是则返回 -1        return left if nums[left] == target else -1

其他应用

快速排序也是另一种基于分治算法的重要排序算法，不像归并排序是按照元素数组中的位置对它们进行划分，快速排序是按照元素的值对它们进行划分。

二叉树遍历中前序、中序和后序遍历都可以用到分治，因为二叉树本身的定义就是将同样类型的树分为两个更小的组成部分——左子树和右子树。

其他如大整数乘法和 Strassen 矩阵乘法也可以巧妙的运用分治算法来获得更好的渐近效率，感兴趣的读者可以继续探索。

参考链接：

• 算法之道（第二版），邹恒明 著：第 3 章 分治与递归

• 算法设计与分析基础(第三版)，Anany Levitin 著，潘彦 译：第 5 章 分治法

• 01.分治算法知识 | 算法通关手册 (itcharge.cn)
  

• Merge Sort in Golang With Examples | Boot.dev