logo标签列表

分治与递归

recursiondivide-and-conquer
18
我想知道分治技术是否总是将问题划分为相同类型的子问题？所谓的相同类型是指可以使用递归函数来实现。分治技术是否总是可以通过递归实现？
谢谢！
8个回答
25

"总是"这个词很可怕，但我无法想象一种分治情况下你不能使用递归的场景。按定义，分治会创建与初始问题相同形式的子问题-这些子问题不断被分解，直到达到某个基本情况，并且分割次数与输入大小相关。递归是这类问题的自然选择。

更多有用信息请参见维基百科文章

2
一个递归问题总是可以用迭代方法来解决，反之亦然。因此，不需要仅使用递归方法来编写分治算法，而尾递归与迭代方法的解决效率相同。 - kgangadhar
函数递归很可能会导致栈溢出错误（是的，这是该网站的名称 ;-）。因此，应使用FIFO循环，其中函数的逻辑将附加任何新问题（而不是再次调用自身）。 - Top-Master
8

分治算法的定义是可以通过递归来解决的。因此答案是肯定的。

1
1
是的。在分治算法技术中，我们将给定的大问题划分为较小的子问题。这些较小的子问题必须类似于大问题，只是规模较小。
例如，对大小为N的数组进行排序的问题与对大小为N/2的数组进行排序的问题没有区别。只是后者问题的规模比前者小。
如果较小的子问题与大问题不相似，则无法使用分治技术来解决大问题。换句话说，仅当给定的大问题可以分解为类似于大问题的较小子问题时，才能使用分治技术来解决给定的问题。
1
检查归并排序算法就足够回答这个问题。了解使用分治（也是递归）实现归并排序算法后，您会看到如果没有递归，它将有多么困难。
实际上，这里最重要的是算法的复杂度，用大O符号和nlogn表示归并排序。
对于归并排序，还有另一个版本，称为“自底向上归并排序”。这是它的简单且非递归版本。
在典型系统上，它比递归的自顶向下归并排序慢约10％。您可以参考以下链接获取更多信息。它在第三节课中有很好的解释。

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

0

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

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

是的，所有的分治算法都可以使用递归来实现。

一个典型的分治算法通常有以下三个步骤：

  1. 分割：将原问题划分为相同类型的子问题。
  2. 解决：递归地解决这些子问题。
  3. 合并：适当地合并答案。

Divide And Conquer

以下是一些标准的分治算法： 1）二分查找， 2）快速排序， 3）归并排序， 4）Strassen算法。
并不是说分治算法必须“总是使用递归”才能实现。从你自己的例子中可以看出，二分查找是一种我们可以轻松地不使用递归来实现的算法。 - RaviU
0

假设P是一个大小为n的问题，S是解决方案。在这种情况下，如果P足够大，可以将其分成子问题，例如P1，P2，P3，P4，...，Pk；假设有k个子问题，每个子问题都有k个解决方案，如S1，S2，S3，...，Sk；现在，如果我们将每个子问题的解决方案组合在一起，就可以得到S的结果。在分治策略中，无论主要问题是什么，所有子问题都必须相同。例如，如果P是排序，则P1，P2和Pn也必须进行排序。因此，这是一种具有递归性质的方法。因此，分治法将是递归的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接