分而治之
在分而治之的方法中,手头的问题被分成更小的子问题,然后每个问题独立解决。当我们继续将子问题划分为更小的子问题时,我们最终可能会到达一个无法再划分的阶段。解决了那些"原子"最小的可能子问题(分数)。最终合并所有子问题的解,得到原问题的解。
从广义上讲,我们可以通过三个步骤来理解
分而治之的方法。
Divide/Break
此步骤涉及将问题分解为更小的子问题。子问题应该代表原始问题的一部分。这一步一般采用递归的方法来划分问题,直到没有子问题可以进一步划分。在这个阶段,子问题本质上是原子的,但仍然代表实际问题的一部分。
Conquer/Solve
这一步接收到很多较小的子问题要解决。一般来说,在这个级别,问题被认为是自己"解决"的。
Merge/Combine
当较小的子问题得到解决时,这个阶段递归地组合它们,直到它们形成原始问题的解决方案。这种算法方法以递归方式工作,并且征服和合并步骤非常接近,以至于它们看起来像一个。
示例
以下计算机算法基于
分而治之编程方法-
合并排序
快速排序
二分搜索
有多种方法可以解决任何计算机问题,但上面提到的是分而治之方法的一个很好的例子。