数据结构 - 分而治之

在分而治之的方法中,手头的问题被分成较小的子问题,然后每个问题都独立解决.当我们继续将子问题划分为更小的子问题时,我们最终可能会达到无法进行更多划分的阶段.解决那些"原子"最小可能的子问题(分数).最后合并所有子问题的解决方案以获得原始问题的解决方案.

Divide并征服

从广义上讲,我们可以分三步了解分而治之方法.

除以/中断

此步骤涉及将问题分解为更小的子问题.子问题应该代表原始问题的一部分.此步骤通常采用递归方法来划分问题,直到子问题不再可被整除为止.在这个阶段,子问题本质上是原子的,但仍然代表实际问题的一部分.

征服/解决

此步骤收到很多较小的子问题有待解决.通常,在这个级别,问题被认为是自己"解决".

合并/合并

当较小的子问题得到解决时,这个阶段递归地组合它们,直到它们形成原始问题的解决方案.这种算法方法递归地工作,并且征服和合并步骤的工作非常接近它们看起来像一个.

示例

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

  • 合并排序

  • 快速排序

  • 二元搜索

  • Strassen的矩阵乘法

  • 最近的一对(点)

有多种方法可以解决任何计算机问题,但所提到的是分而治之的方法的一个很好的例子.