划分和征服和递归

Question

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

谢谢！

Answer 1

“永远”是一个可怕的词，但我想不出一个你不能使用递归的分而治之的情况。根据定义，分而治之创造了与初始问题相同形式的子问题 - 这些子问题不断被分解，直到达到某种基本情况，并且分割数量与输入的大小相关。递归是这种问题的自然选择。

有关更多信息，请参阅Wikipedia article。

Answer 2

根据定义，分而治之算法可以通过递归来解决。所以答案是肯定的。

Answer 3

通常，是的！ Merge sort就是一个例子。这是一个相同的animated version。

Answer 4

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

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

如果较小的子问题与较大的子问题不相似，则分而治之技术不能用于解决更大的问题。换句话说，只有当给定的较大问题可以分成较小的子问题（类似于较大的问题）时，才能使用分而治之技术解决给定问题。

Answer 5

检查合并排序算法对于这个问题就足够了。在理解了具有分而治之（也是递归）的合并排序算法的实现之后，您将看到在没有递归的情况下实现它是多么困难。

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

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

它比典型系统上的递归，自上而下的mergesort慢约10％。您可以参考以下链接获取更多信息。在第3讲好好解释。

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

Answer 6

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

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

Answer 7

是所有除法和征服总是使用递归来实现。

典型的Divide and Conquer算法使用以下三个步骤解决了问题。

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

以下是一些标准算法，即Divide和Conquer算法。 1）二进制搜索，2）快速排序，3）合并排序，4）Strassen算法

Answer 8

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