数据结构&算法 分治算法

• 

  分治算法

  在分治算法中，将手头的问题分成较小的子问题，然后分别解决每个问题。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法再进行划分的阶段。那些“原子的”最小可能的子问题（分数）得以解决。最后合并所有子问题的解决方案，以获得原始问题的解决方案。

  

  从广义上讲，我们可以通过三步过程来理解分治算法。
• 

  分割问题

  此步骤涉及将问题分解为较小的子问题。子问题应该代表原始问题的一部分。此步骤通常采用递归方法来划分问题，直到没有子问题可以进一步分割为止。在这个阶段，子问题本质上已成为原子问题，但仍代表实际问题的一部分。
• 

  解决子问题

  此步骤收到许多要解决的较小子问题。通常，在此级别上，问题被认为是“已解决”。
• 

  合并子问题

  当较小的子问题解决后，此阶段将它们递归组合，直到它们为原始问题制定了解决方案。这种算法方法递归工作，合并步骤如此接近，以至于它们看起来像一个。
• 

  例子

  以下计算机算法基于分治法编程方法-

  • 归并排序
  • 快速排序
  • 二分查找
  • Strassen矩阵乘法
  • 最近对（点）