5

在我的大学里，我被要求为斐波那契数列编写一个 JAVA 程序。我使用递归来编写那个程序。

但是，助理讲师说我的算法效率不高，并要求我分析。他补充说，按照惯例，迭代比递归更适合该程序。

如何分析我们的算法？如何检查迭代和递归中的空间和时间复杂度？就在那时，我发现这些事情和程序的正确性一样重要。

4

4 回答 4

5

作为一个拇指规则：

  • 递归对于人类来说很容易理解。但它是基于堆栈的，堆栈始终是有限资源。
  • 迭代是顺序的，同时更容易调试。但有时会导致难以理解的算法，这些算法可以通过递归轻松完成。

因此，只要步骤数限制在可管理的小数内，您就可以进行递归。正如您将确信堆栈永远不会溢出，同时递归代码是compact and elegant.

如果您想探索更多，这些可能会有所帮助。 递归与循环以及 递归或迭代？

编辑 正如@MrP 所指出的，一些特殊的递归可以被一些编译器优化。

于 2013-08-14T06:56:44.963 回答
2

它与算法的复杂性没有任何关系：当您使用递归时 - 每次调用都会在堆栈上创建一个新框架 - 所以如果递归太深，您可能会遇到 StackOverflow :)

通过使用迭代 - 您正在（可能）在相同空间（覆盖参数先前值）上循环运行，从 StackOverflow 的角度来看，这更快且更安全。

于 2013-08-14T06:56:53.413 回答
2

我建议你点击链接http://nptel.iitm.ac.in/courses.php?disciplineId=106并找到一些算法设计和分析的讲座。它设计算法的基本概念。祝你好运。

于 2013-08-14T07:00:43.113 回答
1

斐波那契数列最大的问题是算法的时间复杂度，当您使用简单递归时，您将重新计算所有内容并做很多双重工作。这是因为当您使用计算 fib(n)

int fib(int n) {
  if (n < 2) { return 1; }
  return fib(n-1) + fib(n-2)
}

您将计算 fib(n-1)，它计算 fib(n-2) 和 fib(n-3)。但是为了计算 fib(n)，你已经计算了 fib(n-2)。为了改善这一点，您需要存储临时结果。这通常更容易使用迭代并从 i = 0 到 n 开始。通过这种方式，您可以轻松存储最后两个结果并避免一遍又一遍地计算相同的值。

查看算法是否有效的一种简单方法是尝试解决一些越来越难的示例。您还可以更准确地计算它。以上面的斐波那契为例。调用 fib(n) 会比较复杂O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1（我们只取 1 来表示加法）。让我们假设O(fib(0)) = O(fib(1)) = 1. 这意味着O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9。正如你所看到的，这个系列会比斐波那契系列本身上升得更快！这意味着大量增加的复杂性。当您有一个从 0 到 n 的 for 循环的迭代算法时，您的复杂性将按 n 的顺序扩展，这会更好。

有关更多信息，请查看大 O 符号。

于 2013-08-14T07:06:02.097 回答