在分而治之的方法中,手头的问题被分成较小的子问题,然后每个问题都独立解决.当我们继续将子问题划分为更小的子问题时,我们最终可能会达到无法进行更多划分的阶段.解决那些"原子"最小可能的子问题(分数).最后合并所有子问题的解决方案以获得原始问题的解决方案.
从广义上讲,我们可以分三步了解分而治之方法.
此步骤涉及将问题分解为更小的子问题.子问题应该代表原始问题的一部分.此步骤通常采用递归方法来划分问题,直到子问题不再可被整除为止.在这个阶段,子问题本质上是原子的,但仍然代表实际问题的一部分.
此步骤收到很多较小的子问题有待解决.通常,在这个级别,问题被认为是自己"解决".
当较小的子问题得到解决时,这个阶段递归地组合它们,直到它们形成原始问题的解决方案.这种算法方法递归地工作,并且征服和合并步骤的工作非常接近它们看起来像一个.
以下计算机算法基于分而治之编程方法 :
合并排序
快速排序
二元搜索
Strassen的矩阵乘法
最近的一对(点)
有多种方法可以解决任何计算机问题,但所提到的是分而治之的方法的一个很好的例子.