recursion - 分而治之和递归

Question

我想知道分而治之的技术是否总是将一个问题分成相同类型的子问题？通过相同的类型，我的意思是可以使用具有递归的函数来实现它。分治法总是可以通过递归来实现吗？

谢谢！

Answer 1

“总是”是一个可怕的词，但我想不出不能使用递归的分而治之的情况。根据定义，分治法会产生与初始问题相同形式的子问题——这些子问题会不断分解，直到达到某种基本情况，并且划分的数量与输入的大小相关。递归是此类问题的自然选择。

有关更多有用信息，请参阅Wikipedia 文章。

Answer 2

根据定义，分治算法是一种可以通过递归求解的算法。所以答案是肯定的。

Answer 3

通常，是的！归并排序就是一个例子。这是相同的动画版本。

Answer 4

是的。在分而治之的算法技术中，我们将给定的较大问题划分为较小的子问题。这些较小的子问题必须与较大的问题类似，只是它们的大小更小。

例如，对大小为 N 的数组进行排序的问题与对大小为 N/2 的数组进行排序的问题没有什么不同。除了后者的问题规模小于前者。

如果较小的子问题与较大的问题不相似，那么分治法就不能用于解决较大的问题。换句话说，只有当给定的较大问题可以分为与较大问题相似的较小子问题时，才能使用分而治之技术解决给定问题。

Answer 5

对于这个问题，检查归并排序算法就足够了。在了解了使用分而治之（也包括递归）的合并排序算法的实现之后，您将看到如果不使用递归来实现它是多么困难。

实际上这里最重要的是算法的复杂性，它用 big-oh 表示法和用于合并排序的 nlogn 表示。

对于合并排序示例，还有另一个版本称为自下而上合并排序。它是简单且非递归的版本。

它比典型系统上的递归、自上而下的归并排序慢约 10%。您可以参考以下链接了解更多信息。在第 3 课中有很好的解释。

https://www.coursera.org/learn/introduction-to-algorithms#

Answer 6

递归是一种编程方法，您可以在其中根据自身定义函数。该函数通常通过稍微修改的参数调用自身（为了收敛）。

1. 将问题分成两个或更多更小的子问题。
2. 通过（递归）解决子问题来征服子问题。
3. 将子问题的解决方案组合成原始问题的解决方案。

Answer 7

是的，所有分而治之总是使用递归来实现。

典型的分治算法使用以下三个步骤解决问题。

1. 划分：将给定问题分解为相同类型的子问题。
2. 征服：递归解决这些子问题
3. 结合：适当地结合答案

以下是一些标准算法，即分而治之算法。1) 二分查找，2) 快速排序，3) 合并排序，4) Strassen 算法

Answer 8

想象P是大小的问题n并且S是解决方案。在这种情况下，如果P足够大，可以划分为子问题，例如P1, P2, P3, P4, ... , Pk; 假设 k 个子问题，并且每个 k 个子问题都会有 k 个解决方案，例如S1, S2, S3, ... , Sk; 现在，如果我们将子问题的每个解决方案组合在一起，我们可以得到 S 结果。在分而治之的策略中，主要问题是什么，所有子问题都必须相同。例如 if Pis sort 那么P1,P2也Pn必须是 sort 。这就是它本质上是递归的方式。因此，分而治之将是递归的。