分治
什么是分治
「分治 divide and conquer」，全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。
- 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
- 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
如何判断分治问题
- 问题可以被分解：原问题可以被分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
- 子问题是独立的：子问题之间是没有重叠的，互相没有依赖，可以被独立解决。
- 子问题的解可以被合并：原问题的解通过合并子问题的解得来。
分治问题优化点
- 操作数量优化：如果我们把子数组不断地再从中点划分为两个子数组，直至子数组只剩一个元素时停止划分，这种思路实际上就是“归并排序”，时间复杂度为 𝑂(𝑛 log 𝑛) 。
- 并行计算优化：分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的时间复杂度，还有利于操作系统的并行优化。并行优化在多核或多处理器的环境中尤其有效，因为系统可以同时处理多个子问题，更加充分地利用计算资源，从而显著减少总体的运行时间。
分治问题的应用
数据结构
- 二分查找：二分查找是将有序数组从中点索引分为两部分，然后根据目标值与中间元素值比较结果，决定排除哪一半区间，然后在剩余区间执行相同的二分操作。
- 归并排序：文章开头已介绍，不再赘述。
- 快速排序：快速排序是选取一个基准值，然后把数组分为两个子数组，一个子数组的元素比基准值小，另一子数组的元素比基准值大，然后再对这两部分进行相同的划分操作，直至子数组只剩下一个元素。
- 桶排序：桶排序的基本思想是将数据分散到多个桶，然后对每个桶内的元素进行排序，最后将各个桶的元素依次取出，从而得到一个有序数组。
- 树：例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等，它们的查找、插入和删除等操作都可以视为分治的应用。
- 堆：堆是一种特殊的完全二叉树，其各种操作，如插入、删除和堆化，实际上都隐含了分治的思想。
- 哈希表：虽然哈希表来并不直接应用分治，但某些哈希冲突解决策略间接应用了分治策略，例如，链式地址中的长链表会被转化为红黑树，以提升查询效率。
算法问题
- 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后再找出跨越两部分的最近点对。
- 大整数乘法：例如 Karatsuba 算法，它是将大整数乘法分解为几个较小的整数的乘法和加法。
- 矩阵乘法：例如 Strassen 算法，它是将大矩阵乘法分解为多个小矩阵的乘法和加法。
- 汉诺塔问题：汉诺塔问题可以视为典型的分治策略，通过递归解决。
- 求解逆序对：在一个序列中，如果前面的数字大于后面的数字，那么这两个数字构成一个逆序对。求解逆序对问题可以通过分治的思想，借助归并排序进行求解。
经典问题
构建二叉树问题
Q:给定一个二叉树的前序遍历 preorder 和中序遍历 inorder ，请从中构建二叉树，返回二叉树的根节点。
class TreeNode: def __init__(self, val) -> None: self.val = val self.left = None self.right = None def split_left_right(preorder, inorder, hashmap, i, l, r): if r - l < 0: return None m = hashmap[preorder[i]] root = TreeNode(preorder[i]) root.left = split_left_right(preorder, inorder, hashmap, i+1, l, m-1) root.right = split_left_right(preorder, inorder, hashmap, i+1+m-l, m+1, r) return root def build_tree(preorder, inorder): hashmap = {val: ix for ix, val in enumerate(inorder)} node = split_left_right(preorder, inorder, hashmap, 0, 0, len(preorder)-1) return node
汉诺塔问题
Q:给定三根柱子，记为 A、B 和 C 。起始状态下，柱子 A 上套着 𝑛 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 𝑛 个圆盘移到柱子 C 上，并保持它们的原有顺序不变。在移动圆盘的过程中，需要遵守以下规则。1. 圆盘只能从一个柱子顶部拿出，从另一个柱子顶部放入。2. 每次只能移动一个圆盘。3. 小圆盘必须时刻位于大圆盘之上。
class Pillar: def __init__(self, name, num) -> None: self.name = name self.lst = [] for _ in range(num): self.lst.append(f'{self.name}{_}') def move(src, buf, tar): val = src.lst.pop(0) tar.lst.append(val) print(f'把{src.name}的{val}移动到{tar.name}上', end='\t') print(f'现在{src.name}上为{src.lst}', end='\t') print(f'现在{tar.name}上为{tar.lst}', end='\t') print(f'现在{buf.name}上为{buf.lst}', end='\n') def dfs(i, src, buf, tar): if i == 1: return move(src, buf, tar) dfs(i-1, src, tar, buf) move(src, buf, tar) dfs(i-1, buf, src, tar) def hanota(i): pillar_a =Pillar('A', i) pillar_b =Pillar('B', 0) pillar_c =Pillar('C', 0) dfs(i, pillar_a, pillar_b, pillar_c)
重点回归
- 分治算法是一种常见的算法设计策略，包括分（划分）和治（合并）两个阶段，通常基于递归实现。
- 判断是否是分治算法问题的依据包括：问题能否被分解、子问题是否独立、子问题是否可以被合并。
- 归并排序是分治策略的典型应用，其递归地将数组划分为等长的两个子数组，直到只剩一个元素时开始逐层合并，从而完成排序。
- 引入分治策略往往可以带来算法效率的提升。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。
- 分治既可以解决许多算法问题，也广泛应用于数据结构与算法设计中，处处可见其身影。
- 相较于暴力搜索，自适应搜索效率更高。时间复杂度为 𝑂(log 𝑛) 的搜索算法通常都是基于分治策略实现的。
- 二分查找是分治策略的另一个典型应用，它不包含将子问题的解进行合并的步骤。我们可以通过递归分治实现二分查找。
- 在构建二叉树问题中，构建树（原问题）可以被划分为构建左子树和右子树（子问题），其可以通过划分前序遍历和中序遍历的索引区间来实现。
- 在汉诺塔问题中，一个规模为 𝑛 的问题可以被划分为两个规模为 𝑛 − 1 的子问题和一个规模为 1 的子问题。按顺序解决这三个子问题后，原问题随之得到解决。
