3

我有一个使用递归打印斐波那契数列的程序。有更好的方法，但我被要求使用递归，所以我不得不这样做。

这是程序：

#include <stdio.h>
#define TERMS 10

long fibo(int);

int main(void){
   for(int i = 1; i <= TERMS; i++) {
       printf("%ld", fibo(i));
   }
   return 0;
}

long fibo(int n){
    if (n < 3) {
        return 1;
    }
    else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

我知道这对于斐波那契数列来说确实是一种糟糕的方法，从上面可以清楚地看出，当TERMS超过 35 时，程序需要很长时间才能完成。

我已经完成了这个答案，无法理解他们是如何解决的，但看起来像

fibo(int n) 的时间复杂度为 O(2^n)

同样，我可能完全错了，但我想要的是：

这个完整程序的时间复杂度是多少，简要解释一下你是如何计算的？

如果您有更好的使用递归计算斐波那契的方法，也欢迎。

4

3 回答 3

8

c(fibo(n)) = c(fibo(n - 1)) + c(fibo(n - 2)) + O(1)

请注意，复杂度遵循与序列一样的精确公式，因为所有计算分支始终以值为 1 的叶结尾，因此可以通过斐波那契数列本身的封闭公式准确计算出精确的 (theta) 复杂度

斐波那契封闭式

但这超出了您的问题范围，我们需要注意的是

c(fibo(n)) < 2 * c(fibo(n - 1))

我们现在需要的只是求解由下式定义的上界级数

an = 2 * an-1 (a1,2 = 1)

结果是

一个 = 2^n

所以，你得到了你想要的 2^n 的上 O 界。

如果你运行它几次你会得到

sigma(c(fib(n))) 从 1 到 TERMS = O(2^(TERMS + 1) - 1)

这是一个简单的数学事实，这意味着在你的情况下（TERMS = 10）你得到

2^11 - 1 = 2047

至于您关于递归执行此操作的更好方法的问题...

int fib(int n, int val = 1, int prev = 0)
{
    if (n == 0) {
        return prev;
    }
    if (n == 1) {
        return val;
    }
    return fib(n - 1, val + prev, val);
}

这就是所谓的尾递归，需要 O(n) （实际上它可以通过一个好的编译器进行优化以实现为循环，然后也会消耗恒定的内存消耗）

于 2017-12-18T15:02:45.620 回答
4

总的来说，它背后有数学，斐波那契在那里解释：https ://en.wikipedia.org/wiki/Recurrence_relation

如果您不必证明它而只需要正确地写下来，您只需要考虑算法的行为方式以及某个数字的重复次数，然后您可以尝试将其推广到任何输入n。

纸是你的朋友！

如果你的递归中有值为“10”的斐波那契，你基本上是在说（10 的斐波那契是 9 的斐波那契 + 8 的斐波那契）

然后你说斐波那契 9 - 它是斐波那契 8 + 斐波那契 7 等等。

您可以绘制图表：

在此处输入图像描述

我认为很明显它将继续成为几乎完整的二叉树。而且您可以看到，对于每个级别，节点的数量都会增加一倍，因此fib(10)它会在底部几乎重复 10 次2^10，因此fib(n)它将是2^n。

如何使其在递归算法中有效？嗯，你可以从图片中看到，即 fib(7) 被求解了 3 次。所以你必须记住 fib(n) 一旦你计算了它。它可以是全局变量，也可以通过递归调用传递对对象的引用。

那你不只是说“fib(n-1)和fib(n-2)”，你先看看“fib(n-1)算不算”？如果是这样，请使用计算值而不是递归。

于 2017-12-18T15:19:33.627 回答
1

生成斐波那契数列的递归函数生成高度为n的二叉树。假设我们取n = 5。然后树结构将是这样的：

fib-递归树

在最底层，我们最终会得到大约 2^ n 个节点。因此，时间复杂度将在O(2^n)左右，因为递归将针对每个叶节点重复。

我们可以通过使用 memoization 的动态编程方法来显着改进这一点，它基本上是将重复的子问题（如示例中的fib(2)或fib(3)在示例中）存储在某种查找表中。这将时间复杂度降低到O(n)。

于 2020-09-19T00:39:39.293 回答