分治法

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

这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、大数乘法（Karatsuba算法）、Q1209543、语法解析（如Q15419395）、Q21055608，以及离散傅里叶变换（FFT）。

另一方面，理解及设计分治法算法的能力需要一定时间去掌握。正如以归纳法去证明一个理论，为了使递归能够推行，很多时候需要用一个较为概括或复杂的问题去取代原有问题。而且并没有一个系统性的方法去适当地概括问题。

分治算法通常以数学归纳法来验证。而它的计算成本则多数以解递回关系式来判定。

## 分而治之

<image>

分治法程式设计范式常用于求解问题的最优解。其基本思想是：将一个给定问题分解为两个或多个更简单的相似子问题，依次求解，再组合各子问题的解以解决原问题；足够简单的问题则直接求解。例如，对 n 个自然数组成的列表进行排序，可将其拆分为各含约 n/2 个数的两个列表，分别排序后再适当交错合并，即得排序结果（见示意图）。此方法即称为归并排序算法。

分治法这个名称有时亦会用于将问题简化为只有一个细问题的算法，例如用于在已排序的列中寻找其中一项的折半搜索算法（或是在数值分析中类似的勘根算法）。这些算法比一般的分治算法更能有效地执行。其中，假如算法使用尾部递归的话，便能转换成简单的循环。但在这广义之下，所有使用递归或循环的算法均被视作“分治算法”。因此，有些作者考虑“分治法”这个名称应只用于每个有最少两个子问题的算法。而只有一个子问题的曾被建议使用减治法这个名称。

分治法的一个重要应用在于最优化：若在每个步骤中能以常数因子缩减（“剪枝”）搜索空间，则整体算法与剪枝步骤具有相同的渐近复杂度，常数取决于剪枝因子（通过对几何级数求和可得）；此方法称为剪枝搜寻。

## 早期历史上的先例

早期的此类算法主要是减治算法——原始问题被逐步拆分为单个子问题，实际上可以以迭代方式求解。

折半搜索算法——一个将原来问题连逐地拆细成大约一半大小的单一子问题的分治算法——拥有一段悠长历史。虽然算法在计算机上的清楚描述出现在1946年约翰莫齐利（John Mauchly）的一篇文章里，然而利用已排序的物件序列去加快搜寻的构想早已在公元前200年的巴比伦尼亚出现。另一个单一子问题的分治算法是找出2个数的最大公因数的辗转相除法（透过将数字化小至使子问题变得简单），于公元前数世纪已经出现。

一个早期有多个子问题的分治算法是高斯在1805年描述关于快速傅立叶变换的算法，尽管他没有量化地分析它的操作数目，而快速傅立叶变换直至在一世纪之后被重新发现之前亦没有广泛流传。这个算法现在称为库利－图基快速傅里叶变换算法。

至于专门用于计算机之上而且正确地分析的分治算法早期例子，则可以数到约翰·冯·诺伊曼于1945年发明的归并排序。

另一个显著的例子是Anatolii Alexeevitch Karatsuba于1960年发明在$O(n^{\log_2 3})$步骤内将两个n位数相乘的Karatsuba算法。它反证了安德雷·柯尔莫哥洛夫于1956年认为这个乘法需要$\Omega(n^2)$步骤的猜想。

高德纳举了一个最初并没有涉及计算机的分治算法例子，就是一般邮局用于分发信件的方法：信件在主要邮局根据不同的地理范围而分到不同的袋里，每个袋亦在运送到地区邮局时分到更小的袋里，如是者直至信件被派发为止。这个方法与早于1929年的打孔卡排序机所用的基数排序相类同。

## 优势

### 解决困难问题

分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。比如，汉诺塔问题如果采用分治算法，可以把高度为n的塔的问题转换成高度为n-1的塔来解决，如此重复，直至问题化简到可以很容易的处理为止。

### 算法效率

人们发现有很多效率很高的分治算法，比如，Karatsuba快速乘法算法、快速排序算法和并行算法、矩阵乘法的施特拉森算法、快速傅里叶变换等。

在以上所有示例中，分治法使得解的渐近代价得到改善。例如，若（a）基本情况的规模有常数上界，分解问题与合并部分解所需的工作量与问题规模 $n$ 成正比，且（b）每个阶段有数量有界的 $p$ 个规模约为 $\frac{n}{p}$ 的子问题，则分治算法的代价为 $O(n\log_{p}n)$。

对于其他类型的分治方法，运行时间亦可加以推广。例如，设（a）分解问题与合并部分解耗时 $cn$，其中 $n$ 为输入规模，$c$ 为某常数；（b）当 $n < 2$ 时，算法耗时有上界 $c$；（c）共有 $q$ 个子问题，每个规模约为 $\frac{n}{2}$，则运行时间如下：

- 若子问题数目 $q > 2$，则分治算法的运行时间上界为 $O(n^{\log_{2}q})$。
- 若子问题数目恰好为一，则分治算法的运行时间上界为 $O(n)$。

若分解问题与合并部分解耗时 $cn^2$，且共有2个规模各为 $\frac{n}{2}$ 的子问题，则分治算法的运行时间上界为 $O(n^2)$。

### 同步性

分治算法天然适合在多处理器机器上执行，尤其是共享内存系统——在此类系统中，不同子问题可在不同处理器上执行，处理器之间的数据通信无需提前规划。

### 内存存取

分治算法天然倾向于高效利用内存快取。原因在于：一旦子问题规模足够小，它及其所有子问题原则上均可在快取内求解，而无需访问较慢的主内存。以这种方式设计以利用快取的算法称为Q5015938，因为它不将快取大小作为显式参数。此外，分治算法可被设计为重要算法（如排序、FFT及矩阵乘法）的最优快取无关算法——在渐近意义上，无论快取大小如何，均能以可能最优的方式使用快取。相比之下，利用快取的传统方法是“分块”（如Q6675847中的做法），即将问题显式地分割为适当大小的块——此方法同样可最优地使用快取，但仅在算法针对特定机器的快取大小调优时才有效。

同样的优势亦存在于其他分层存储系统中，例如NUMA或虚拟内存，以及多级快取：一旦子问题规模足够小，即可在存储层次结构的某一层内求解，而无需访问更高（更慢）的层次。

### 修正控制

在含舍入运算的计算中（例如使用浮点数时），分治算法可能比表面等价的迭代方法产生更精确的结果。例如，对 N 个数求和，既可用逐一累加的简单循环，也可用称为Q17104961的分治算法——将数据集一分为二，递归地计算两半之和，再相加。虽然后者执行的加法次数与前者相同，并需承担递归调用的额外开销，但通常精度更高。

## 实现

### 循环递归

分治算法天然以递归过程实现。在此情况下，通往当前求解问题的各部分子问题会自动储存在过程呼叫堆叠中。递归函数是指在其定义中呼叫自身的函数。

在每一层递归上都有三个步骤：

- 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
- 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
- 合并：将各子问题的解合并为原问题的解。

### 显堆栈

分治算法亦可以非递归程序实现，将各部分子问题储存在某种显式数据结构中，如堆叠、伫列或优先伫列。此方法在选择下一个待求解子问题时提供了更大的自由度，这一特性在某些应用中十分重要——例如广度优先递归和用于函数最优化的分支定界法。对于不支持递归过程的程式语言，此方法亦是标准解决方案。

### 堆叠大小

在分治算法的递归实现中，必须确保为递归堆叠分配了足够的内存，否则执行可能因堆叠溢位而失败。高效率的分治算法通常具有较小的递归深度。例如，快速排序算法可以实现为对 $n$ 个元素排序时嵌套递归呼叫次数不超过 $\log_2 n$ 次。

使用递归过程时，堆叠溢位可能难以预防——许多编译器将递归堆叠视为连续内存块，且有些编译器会为其预留固定大小的空间。此外，编译器可能在递归堆叠上储存多于严格所需的信息，包括返回地址、未更改的参数及过程的局部变量。因此，可通过限制递归过程中的参数和局部变量数目、或以显式堆叠数据结构替代递归，来降低堆叠溢位的风险。

### 基本情况的选择

在任何递归算法中，基本情况——即直接求解以终止递归的小子问题——的选择具有相当大的自由度。

选择尽可能小或尽可能简单的基本情况更为优雅，且通常带来更简洁的程序，因为需要考虑的情况更少、更易求解。例如，快速傅立叶变换算法可在输入为单个样本时停止递归，快速排序算法可在输入为空列表时停止；两者均只有一个基本情况，且无需任何处理。

另一方面，若在规模相对较大的基本情况处停止递归并以非递归方式求解，效率往往可以提升，从而形成Q17092099。这一策略避免了几乎不做任何工作的递归呼叫的开销，也可能允许使用针对这些基本情况比显式递归更高效的专用非递归算法。一种简单混合递归算法的通用方法是短路基本情况，又称臂长递归：在函数呼叫前先检查下一步是否会达到基本情况，以避免不必要的函数呼叫。例如，在树结构中，先检查子节点是否为空再递归，比递归至子节点后再检查是否为空，在某些二叉树算法中可减少约一半的函数呼叫。由于分治算法最终会将每个问题或子问题化为大量基本情况，这些情况通常主导整体算法的代价，尤其是在分割/合并开销较低时。注意，这些考量与递归是由编译器实现还是由显式堆叠实现无关。

因此，许多快速排序库实现会在待排序元素数目足够少时，切换至基于简单循环的插入排序（或类似）算法。值得注意的是，若空列表是唯一的基本情况，对含 $n$ 个元素的列表排序最多需要 $n$ 次仅返回而不做任何工作的快速排序呼叫；将基本情况扩大至规模不超过2的列表，可消除大多数此类空呼叫；更一般地，采用大于2的基本情况规模通常可减少函数呼叫开销或堆叠操作所占的时间比例。

另一种方法是采用较大的基本情况，但仍使用分治算法，并针对一组预定的固定规模将算法完全展开为不含递归、循环或条件判断的代码（与部分求值技术相关）。例如，某些高效FFT实现采用此方法，其基本情况是针对一组固定规模的分治FFT算法的展开实现。源码生成方法可用于高效实现此策略所需的大量独立基本情况。

此思想的推广版本称为递归“展开”或“粗化”，已有多种自动化扩大基本情况过程的技术被提出。

### 重叠子问题的动态规划

对于某些问题，分支递归可能会多次求解同一子问题。在此情况下，识别并保存这些重叠子问题的解可能是值得的，这一技术通常称为记忆化。将此思想推至极限，可引导出自底向上的分治算法，即动态规划。

## 示例

分治法在高级语言中主要的一个思想是递归，LISP语言中的体现出了极丰富的分治法。

以下是归并排序C语言的示例代码，输入参数中，需要排序的数组为array,起始索引为first，终止索引为last。调用完成后，array中从first到last处于升序排列。

```c
 void merge_sort(int array[], unsigned int first, unsigned int last)
 {
 	int mid = 0;
 	if(first<last)
 	{
 		mid = (first+last)/2;
 		merge_sort(array, first, mid);
 		merge_sort(array, mid+1,last);
 		merge(array,first,mid,last);
 	}
 }
```

在程式中可以看出分治法的应用：在merge_sort中，将原来针对索引first到last的数组排序的问题，分为二份较小的问题

- 先针对索引first到mid的数组排序。
- 再针对索引mid+1到last的数组排序。

最后再进行二个数组的合并。