这种分治技术是采用高效算法处理各种问题的基础,例如排序(例如快速排序、归并排序)、大数相乘(例如卡拉津巴算法)、寻找最接近的点对、句法分析(例如自上而下的解析器)以及计算离散傅立叶变换(FFT)。
理解和设计分治算法是一项复杂的技能,需要很好地理解所要解决的潜在问题的本质。当用归纳法证明一个定理时,通常需要用一个更一般或更复杂的问题来代替原来的问题,以便初始化递归,并且没有系统的方法去解决所有类似的问题。当用高效的双重递归优化斐波那契数的计算时,可以看到这些分治的复杂情况。
分治算法的正确性通常通过数学归纳法来证明,其计算成本通常通过求解递归关系来确定。
分而治之的范式经常被用来寻找问题的最佳解决方案。它的基本思想是将一个给定的问题分解成两个或更多相似但更简单的子问题,从而依次解决它们,并组合它们的解决方案来解决给定的问题。对于一些足够简单的问题则被直接解决。例如,要对给定的n个自然数列表进行排序,将其分成两个大约各有n/2个自然数的列表,依次对每个列表进行排序,并适当地对两个结果进行交织排序,以获得给定列表的排序版本(见图)。这种方法被称为归并排序算法。
分治法的一个重要应用是在最优化中,其中如果搜索空间在每一步被常数因子压缩(“删减”),整个算法具有与删减步骤相同的渐近复杂性,常数取决于删减因子(通过对几何级数求和);这就是所谓的修剪和搜索。
这些算法的早期例子主要是减治——原始问题被连续地分解成单个子问题,并且确实可以迭代地解决。
分而治之是解决概念性难题的有力工具:它所需要解决的只是将问题分解成子问题、解决琐碎的子问题以及将子问题解决方法结合起来以解决原始问题。同样,减治法需要将问题简化为一个更小的问题,例如经典的汉诺塔难题,它将移动n层塔简化为移动n-1层塔的子问题,并不断重复最终解决原始问题。
分治模式通常有助于发现一些比较高效算法。例如卡拉津巴的快速乘法、快速排序和归并排序算法、应用于矩阵乘法的斯特拉森算法和快速傅立叶变换。
在所有这些例子中,分治方法导致解的渐近成本得到改善。例如,如果(a)基本情况具有特定范围的大小,则分割问题和组合部分解的工作与问题的大小n成比例,当子问题的范围限定数为P时,在每个阶段,子问题的大小为n/p,那么分治算法的成本将是O(nlogpn)。
分治算法一般均适用于在多处理器机器中执行,尤其是共享内存系统,其中处理器之间的数据通信不需要预先计划,因为不同的子问题可以在不同的处理器上执行。
分治算法一般普遍倾向于有效利用内存缓存。原因是一旦一个子问题足够小,原则上它和它的所有子问题都可以在高速缓存中解决,而无需访问运行较慢的主存储器。以这种方式利用高速缓存设计的算法被称为缓存遗忘算法,因为它不将高速缓存大小作为显式参数。此外,分治算法可以被设计用于重要的算法(例如排序、快速傅立叶变换和矩阵乘法),使之成为最佳的高速缓存遗忘算法——无论高速缓存大小如何,它们都渐近意义上以最佳的方式使用高速缓存。相比之下,利用缓存的传统方法是阻塞,如在循环嵌套优化中,问题被明确划分为适当大小的块——这也可以优化使用缓存,但是这种方法仅局限于当算法针对特定机器的特定缓存大小进行调整的情形。
此外,对于其他分层存储系统(如非统一内存访问架构NUMA或虚拟内存)以及多级高速缓存也存在相同的优势。一旦子问题足够小,就可以在给定的分层级别内解决,而无需访问更高(更慢)的级别。
分治算法普遍采用递归实现。在这种情况下,导致当前正在解决的部分子问题会自动存储在过程调用的堆栈中,递归函数是在其定义内调用自身的函数。
分治算法也可以通过非递归程序来实现,该程序将部分子问题存储在一些显式数据结构中,例如堆栈、队列或优先级队列。这种方法允许在选择下一个要解决的子问题时拥有更多的自由度,这在某些应用中很重要,例如在广度优先递归和函数优化的分支定界方法中。这种方法也是一些不支持递归过程的编程语言的标准解决方案。
当使用递归过程时,堆栈溢出可能很难避免,因为许多编译器假设递归堆栈是一个连续的内存区域,有些编译器会为它分配固定数量的空间。编译器在没有被严格要求时,还可以在递归堆栈中保存更多的信息,例如返回地址、不变的参数和过程的内部变量。因此,可以通过使用显式堆栈结构,最小化递归过程的参数和内部变量,从来降低堆栈溢出的风险。
在任何递归算法中,基本情况的选择都有相当大的自由度,这些小的子问题可以直接解决以终止递归。
选择最小或最简单的基本案例,通常会导致程序更简单优雅,因为需要考虑的案例更少,且更容易解决。例如,当输入是单个采样点时,快速傅立叶变换算法可以停止递归,当输入列表为空时,快速排序列表排序算法可以停止递归;在这两个例子中,只需要考虑一个不需要处理的基本情况。
另一方面,当递归在相对较大的案例下停止,并且这些案例难以采用递归解决时效率通常会提高,从而产生混合算法。这种策略避免了递归调用的开销,而递归调用只做很少工作或不做任何工作的,并且还允许使用专门的非递归算法,对于那些基本案例,这些算法比显式递归更有效。简单混合递归算法的一般过程是将基本案例短路,也称为臂长递归。在这种情况下,在函数调用之前检查下一步是否会出现基本案例,以避免不必要的函数调用。例如,在树中递归之前检查null,而不是递归到子节点后再进行检查,这避免了二叉树上某些算法中一半的函数调用。由于分治算法最终将每个问题或子问题实例减少到大量的基本实例,因此这些通常控制算法的总成本,尤其是当分割/连接开销较低时。请注意,这些考虑并不取决于递归是由编译器实现还是由显式堆栈实现。
对于某些问题,分支递归可能会多次评估相同的子问题。在这种情况下,识别和保存这些重叠子问题的解决方案可能是值得的,这种技术通常被称为记忆。一直到极限,它会导致自下而上的分治算法,如动态编程和图表解析。