Data Structures Algorithms 简明教程

此步骤涉及将问题分解为更小的子问题。子问题应表示原问题的一部分。此步骤通常采用递归方法来划分问题，直到没有任何子问题可以进一步划分为止。在此阶段，子问题的大小变为原子，但仍然表示实际问题的一部分。

此步骤接收许多较小的子问题以求解。通常，在此级别上，问题被认为自己“已解决”。

当较小的子问题得到解决后，此阶段会递归地将它们组合起来，直到它们形成原问题的解决方案。这种算法方法按递归方式工作，分治和合并步骤工作得非常接近，以至于它们看起来像一个整体。

有各种方法可以让各种算法获取输入，以便可以使用分治技术来解决它们。阵列就是其中之一。在需要输入以列表形式出现的算法（如各种排序算法）中，最常使用阵列数据结构。

在下方的排序算法的输入中，阵列输入被细分为子问题，直到无法进一步细分为止。

然后，对子问题进行排序（征服步骤）并将它们合并起来形成原阵列的解决方案（合并步骤）。

由于阵列是索引和线性数据结构，因此排序算法最常使用阵列数据结构来接收输入。

另一个可用于获取分割和征服算法的输入的数据结构是链表（例如，使用链表的归并排序）。与阵列类似，链表也是存储数据序列的线性数据结构。

考虑链表上的归并排序算法；按照非常流行的龟兔算法，将列表分为无法进一步细分为止。

然后，对列表中的节点进行排序（征服）。然后，这些节点以递归方式组合（或合并），直到获得最终解决方案。

还可以采用略有不同的技术，对带链表数据结构执行各种搜索算法，因为带链表不是已编入索引的线性数据结构。必须使用链表节点中可用的指针来对其进行处理。

分而治之方法支持并行性，因为子问题是独立的。因此，使用此技术设计的算法可以在多处理器系统或不同机器上同时运行。

在此方法中，大多数算法都使用递归设计，因此内存管理开销很大。对于递归函数，使用堆栈来存储函数状态。

以下计算机算法基于分而治之编程方法：

有多种方法可以解决任何计算机问题，但上述方法是分而治之方法的一个很好示例。