数据结构&算法 分治算法



  • 分治算法

    分治算法中,将手头的问题分成较小的子问题,然后分别解决每个问题。当我们继续将子问题划分为更小的子问题时,我们最终可能会达到无法再进行划分的阶段。那些“原子的”最小可能的子问题(分数)得以解决。最后合并所有子问题的解决方案,以获得原始问题的解决方案。
    dsa
    从广义上讲,我们可以通过三步过程来理解分治算法
  • 分割问题

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

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

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

    以下计算机算法基于分治法编程方法-
    • 归并排序
    • 快速排序
    • 二分查找
    • Strassen矩阵乘法
    • 最近对(点)