分而治之算法

分而治之的范式经常被用来寻找问题的最佳解决方案。它的基本思想是将一个给定的问题分解成两个或更多相似但更简单的子问题，从而依次解决它们，并组合它们的解决方案来解决给定的问题。对于一些足够简单的问题则被直接解决。例如，要对给定的n个自然数列表进行排序，将其分成两个大约各有n/2个自然数的列表，依次对每个列表进行排序，并适当地对两个结果进行交织排序，以获得给定列表的排序版本(见图)。这种方法被称为归并排序算法。

“分而治之”这个名称有时被用于将每个问题简化为一个子问题的算法，例如用于在排序列表中查找记录的二分搜索算法(或其在数值计算中的模拟算法，用于寻找根的二分算法)。^[1] 这些算法可以比一般的分治算法的实现更为有效；特别是，如果它们使用尾部递归，则可以将它们转换成简单的循环。然而，广义下，每一种使用递归或循环的算法都可以被视为“分治算法”。因此，一些作者认为，只有当每个问题可能产生两个或更多子问题时，才应该使用“分治”这个名称。^[2] 因此，“减治法”已经被提出来，用于代替单个子问题类。^[3]

分治法的一个重要应用是在最优化中，其中如果搜索空间在每一步被常数因子压缩(“删减”)，整个算法具有与删减步骤相同的渐近复杂性，常数取决于删减因子(通过对几何级数求和)；这就是所谓的修剪和搜索。

这些算法的早期例子主要是减治——原始问题被连续地分解成单个子问题，并且确实可以迭代地解决。

二分查找法是一种减治的算法，其中子问题的大小大约是原始问题大小的一半，它有着悠久的历史。虽然约翰·毛克利在1946年的一篇文章中对计算机上的算法进行了清晰的描述，但使用排序后的列表来方便搜索的想法至少可以追溯到公元前200年的巴比伦尼亚。^[4] 另一个古老的-减治算法是欧几里德算法，它通过将两个数减少到越来越小的等价子问题来计算两个数的最大公约数，这可以追溯到公元前几个世纪。

应用于多个子问题的分治算法的一个早期例子是高斯于1805年对现在被称为库利-图基快速傅里叶变换(FFT)算法的描述，^[5] 尽管他没有定量分析其运算量的大小，但是直到一个多世纪后FFT算法才被重新发现而得到广泛应用。

一个早期应用于两个子问题分治算法是约翰·冯·诺依曼在1945年发明的专门为计算机开发的并经过适当分析的归并排序算法。^[6]

另一个值得注意的例子是Anatolii A. Karatsuba在1960年^[7] 发明的算法，该算法可以在   复杂度内将两个n位数相乘(用大0表示法)。这个算法推翻了安德烈·科尔莫戈罗夫1956年提出的计算该问题需要的步骤不小于   的猜想。

作为最初不涉及计算机的分治算法的另一个例子，唐纳德·克努特提出了邮局通常用来发送邮件的方法:信件被分类到不同地理区域的不同袋子中，每个袋子本身被分类到较小的子区域的批次中，依此类推，直到它们被投递，这与在1929年就为穿孔卡片分类机所使用的基数排序方法类似。^[4]

3.1 解决难题

分而治之是解决概念性难题的有力工具:它所需要解决的只是将问题分解成子问题、解决琐碎的子问题以及将子问题解决方法结合起来以解决原始问题。同样，减治法需要将问题简化为一个更小的问题，例如经典的汉诺塔难题，它将移动n层塔简化为移动n-1层塔的子问题，并不断重复最终解决原始问题。

3.2 算法效率

分治模式通常有助于发现一些比较高效算法。例如卡拉津巴的快速乘法、快速排序和归并排序算法、应用于矩阵乘法的斯特拉森算法和快速傅立叶变换。

在所有这些例子中，分治方法导致解的渐近成本得到改善。例如，如果(a)基本情况具有特定范围的大小，则分割问题和组合部分解的工作与问题的大小n成比例，当子问题的范围限定数为P时，在每个阶段，子问题的大小为n/p，那么分治算法的成本将是O(n log_pn)。

3.3 并行

分治算法一般均适用于在多处理器机器中执行，尤其是共享内存系统，其中处理器之间的数据通信不需要预先计划，因为不同的子问题可以在不同的处理器上执行。

3.4 存储访问

分治算法一般普遍倾向于有效利用内存缓存。原因是一旦一个子问题足够小，原则上它和它的所有子问题都可以在高速缓存中解决，而无需访问运行较慢的主存储器。以这种方式利用高速缓存设计的算法被称为缓存遗忘算法，因为它不将高速缓存大小作为显式参数。此外，分治算法可以被设计用于重要的算法(例如排序、快速傅立叶变换和矩阵乘法)，使之成为最佳的高速缓存遗忘算法——无论高速缓存大小如何，它们都渐近意义上以最佳的方式使用高速缓存。相比之下，利用缓存的传统方法是阻塞，如在循环嵌套优化中，问题被明确划分为适当大小的块——这也可以优化使用缓存，但是这种方法仅局限于当算法针对特定机器的特定缓存大小进行调整的情形。

此外，对于其他分层存储系统(如非统一内存访问架构NUMA或虚拟内存)以及多级高速缓存也存在相同的优势。一旦子问题足够小，就可以在给定的分层级别内解决，而无需访问更高(更慢)的级别。

3.5 舍入控制

在使用舍入算法(例如浮点数)的计算中，分治算法可能比表面等价的迭代方法产生更精确的结果。例如，可以通过简单的循环将每个数据赋给单个变量，或者通过称为成对求和的分治算法将数据集分成两半，递归计算每一半的和，然后将两个和相加。虽然第二种方法执行与第一种方法相同数量的加法，并承担递归调用的额外开销，但它通常更准确。^[8]

4.1 递归

分治算法普遍采用递归实现。在这种情况下，导致当前正在解决的部分子问题会自动存储在过程调用的堆栈中，递归函数是在其定义内调用自身的函数。

4.2 显式堆栈

分治算法也可以通过非递归程序来实现，该程序将部分子问题存储在一些显式数据结构中，例如堆栈、队列或优先级队列。这种方法允许在选择下一个要解决的子问题时拥有更多的自由度，这在某些应用中很重要，例如在广度优先递归和函数优化的分支定界方法中。这种方法也是一些不支持递归过程的编程语言的标准解决方案。

4.3 堆栈大小

在分治算法的递归实现中，必须确保为递归堆栈分配足够的内存，否则算法的执行可能会因为堆栈溢出而失败。具有较高时间效率的分治算法通常具有相对较小的递归深度。例如，嵌套递归的次数可以控制在   内是基于快速排序算法对   个项目进行排序。

当使用递归过程时，堆栈溢出可能很难避免，因为许多编译器假设递归堆栈是一个连续的内存区域，有些编译器会为它分配固定数量的空间。编译器在没有被严格要求时，还可以在递归堆栈中保存更多的信息，例如返回地址、不变的参数和过程的内部变量。因此，可以通过使用显式堆栈结构，最小化递归过程的参数和内部变量，从来降低堆栈溢出的风险。

4.4 选择基本案例

在任何递归算法中，基本情况的选择都有相当大的自由度，这些小的子问题可以直接解决以终止递归。

选择最小或最简单的基本案例，通常会导致程序更简单优雅，因为需要考虑的案例更少，且更容易解决。例如，当输入是单个采样点时，快速傅立叶变换算法可以停止递归，当输入列表为空时，快速排序列表排序算法可以停止递归；在这两个例子中，只需要考虑一个不需要处理的基本情况。

另一方面，当递归在相对较大的案例下停止，并且这些案例难以采用递归解决时效率通常会提高，从而产生混合算法。这种策略避免了递归调用的开销，而递归调用只做很少工作或不做任何工作的，并且还允许使用专门的非递归算法，对于那些基本案例，这些算法比显式递归更有效。简单混合递归算法的一般过程是将基本案例短路，也称为臂长递归。在这种情况下，在函数调用之前检查下一步是否会出现基本案例，以避免不必要的函数调用。例如，在树中递归之前检查null，而不是递归到子节点后再进行检查，这避免了二叉树上某些算法中一半的函数调用。由于分治算法最终将每个问题或子问题实例减少到大量的基本实例，因此这些通常控制算法的总成本，尤其是当分割/连接开销较低时。请注意，这些考虑并不取决于递归是由编译器实现还是由显式堆栈实现。

因此，例如，一旦要排序的项目数量足够少，快速排序的许多库实现将切换到简单的基于循环的插入排序(或类似)算法。特别的，如果空列表是唯一的基本情况，对包含n个条目的列表进行排序将最多需要n个快速排序调用，这些调用除了立即返回之外不产生其他操作。将基本案例增加到大小为2或更小的列表将消除大多数无意义的调用，更一般地说，大于2的基本案例通常用于减少花费在函数调用开销或堆栈操作上的时间。

或者，仍然可以使用具有大型基本案例的分治算法，但是针对固定大小的预定集合实现该算法，其中该算法可以完全展开为没有递归、循环或条件的代码(与部分评估技术相关)。例如，这种方法用于一些有效的快速傅立叶变换实现，其中基本情况是一组固定大小的分治快速傅立叶变换算法的展开实现。^[9] 源代码生成方法可以用来生成大量独立的基本案例，以有效地实现这一策略。^[9]

这种思想的广义版本被称为递归“展开”或“粗化”，并且已经提出了各种技术来自动化扩展基本用例的使用范围。^[10]

4.5 共享重复的子问题

对于某些问题，分支递归可能会多次评估相同的子问题。在这种情况下，识别和保存这些重叠子问题的解决方案可能是值得的，这种技术通常被称为记忆。一直到极限，它会导致自下而上的分治算法，如动态编程和图表解析。