分治算法简介分治算法|算法设计与分析

分而治之是一种算法模式。在算法方法中, 设计是对巨大输入进行争议, 将输入分成小块, 在每个小块上确定问题, 然后将分段解决方案合并为全局解决方案。解决问题的这种机制称为分而治之策略。
分而治之算法由使用以下三个步骤的争议组成。

将原始问题分为一组子问题。
征服：递归地分别解决每个子问题。
合并：将子问题的解决方案放在一起, 以得到整个问题的解决方案。

文章图片
通常, 我们可以在三步过程中遵循分而治之的方法。
示例：具体的计算机算法基于分而治之方法：

最大和最小问题
二元搜寻
排序（合并排序, 快速排序）
河内塔。

分而治之基础分而治之策略有两个基本原则：

关系公式
停止条件

1.关系公式：这是我们从给定技术中生成的公式。在生成公式之后, 我们将应用D＆C策略, 即, 我们递归解决问题并解决破碎的子问题。
【分治算法简介】2.停止条件：当我们使用分而治之策略解决问题时, 我们需要知道需要花多少时间应用分而治之。因此, 需要停止D＆C递归步骤的条件称为“停止条件”。