Data Structures Algorithms 简明教程
Divide & Conquer Algorithm
使用分而治之的方法，手头的问题被分解为更小的子问题，然后独立解决每个问题。当我们继续将子问题细分为更小的子问题时，我们可能最终达到无法进一步细分的状态。那些最小的可能子问题使用原始解决方案来解决，因为它需要更少的时间来计算。所有子问题的解决方案最终合并在一起，以获得原问题的解决方案。
Using divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep dividing the sub-problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those smallest possible sub-problems are solved using original solution because it takes lesser time to compute. The solution of all sub-problems is finally merged in order to obtain the solution of the original problem.
从广义上讲，我们可以通过三个步骤理解 @ {s0} 方法。
Broadly, we can understand divide-and-conquer approach in a three-step process.
Divide/Break
此步骤涉及将问题分解为更小的子问题。子问题应表示原问题的一部分。此步骤通常采用递归方法来划分问题，直到没有任何子问题可以进一步划分为止。在此阶段，子问题的大小变为原子，但仍然表示实际问题的一部分。
This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in size but still represent some part of the actual problem.
Conquer/Solve
此步骤接收许多较小的子问题以求解。通常，在此级别上，问题被认为自己“已解决”。
This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered 'solved' on their own.
Merge/Combine
当较小的子问题得到解决后，此阶段会递归地将它们组合起来，直到它们形成原问题的解决方案。这种算法方法按递归方式工作，分治和合并步骤工作得非常接近，以至于它们看起来像一个整体。
When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one.
Arrays as Input
有各种方法可以让各种算法获取输入，以便可以使用分治技术来解决它们。阵列就是其中之一。在需要输入以列表形式出现的算法（如各种排序算法）中，最常使用阵列数据结构。
There are various ways in which various algorithms can take input such that they can be solved using the divide and conquer technique. Arrays are one of them. In algorithms that require input to be in the form of a list, like various sorting algorithms, array data structures are most commonly used.
在下方的排序算法的输入中，阵列输入被细分为子问题，直到无法进一步细分为止。
In the input for a sorting algorithm below, the array input is divided into subproblems until they cannot be divided further.
然后，对子问题进行排序（征服步骤）并将它们合并起来形成原阵列的解决方案（合并步骤）。
Then, the subproblems are sorted (the conquer step) and are merged to form the solution of the original array back (the combine step).
由于阵列是索引和线性数据结构，因此排序算法最常使用阵列数据结构来接收输入。
Since arrays are indexed and linear data structures, sorting algorithms most popularly use array data structures to receive input.
Linked Lists as Input
另一个可用于获取分割和征服算法的输入的数据结构是链表（例如，使用链表的归并排序）。与阵列类似，链表也是存储数据序列的线性数据结构。
Another data structure that can be used to take input for divide and conquer algorithms is a linked list (for example, merge sort using linked lists). Like arrays, linked lists are also linear data structures that store data sequentially.
考虑链表上的归并排序算法；按照非常流行的龟兔算法，将列表分为无法进一步细分为止。
Consider the merge sort algorithm on linked list; following the very popular tortoise and hare algorithm, the list is divided until it cannot be divided further.
然后，对列表中的节点进行排序（征服）。然后，这些节点以递归方式组合（或合并），直到获得最终解决方案。
Then, the nodes in the list are sorted (conquered). These nodes are then combined (or merged) in recursively until the final solution is achieved.
还可以采用略有不同的技术，对带链表数据结构执行各种搜索算法，因为带链表不是已编入索引的线性数据结构。必须使用链表节点中可用的指针来对其进行处理。
Various searching algorithms can also be performed on the linked list data structures with a slightly different technique as linked lists are not indexed linear data structures. They must be handled using the pointers available in the nodes of the list.
Pros and cons of Divide and Conquer Approach
分而治之方法支持并行性，因为子问题是独立的。因此，使用此技术设计的算法可以在多处理器系统或不同机器上同时运行。
Divide and conquer approach supports parallelism as sub-problems are independent. Hence, an algorithm, which is designed using this technique, can run on the multiprocessor system or in different machines simultaneously.
在此方法中，大多数算法都使用递归设计，因此内存管理开销很大。对于递归函数，使用堆栈来存储函数状态。
In this approach, most of the algorithms are designed using recursion, hence memory management is very high. For recursive function stack is used, where function state needs to be stored.
Examples of Divide and Conquer Approach
以下计算机算法基于分而治之编程方法：
The following computer algorithms are based on divide-and-conquer programming approach −
有多种方法可以解决任何计算机问题，但上述方法是分而治之方法的一个很好示例。
There are various ways available to solve any computer problem, but the mentioned are a good example of divide and conquer approach.