logo图片
数据结构与算法

分而治之

在分而治之的方法中,手头的问题被分成更小的子问题,然后每个问题独立解决。当我们继续将子问题划分为更小的子问题时,我们最终可能会到达一个无法再划分的阶段。解决了那些"原子"最小的可能子问题(分数)。最终合并所有子问题的解,得到原问题的解。
分而治之
从广义上讲,我们可以通过三个步骤来理解 分而治之的方法。

Divide/Break

此步骤涉及将问题分解为更小的子问题。子问题应该代表原始问题的一部分。这一步一般采用递归的方法来划分问题,直到没有子问题可以进一步划分。在这个阶段,子问题本质上是原子的,但仍然代表实际问题的一部分。

Conquer/Solve

这一步接收到很多较小的子问题要解决。一般来说,在这个级别,问题被认为是自己"解决"的。

Merge/Combine

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

示例

以下计算机算法基于 分而治之编程方法-
合并排序 快速排序 二分搜索
有多种方法可以解决任何计算机问题,但上面提到的是分而治之方法的一个很好的例子。
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4