这个递归Fibonacci的大时间复杂度？

Question

我有一个使用递归打印斐波纳契数列的程序.有更好的方法,但我被要求使用递归,所以我必须这样做.

这是程序:

#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);
    }
}

我知道这对于Fibonacci系列来说真的是一个糟糕的方法,从上面可以清楚地看到,因为TERMS超过35,该程序需要花费大量时间才能完成.

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

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

我可能也完全错了,但我想要的只是:

这个完整程序的时间复杂度是什么,简要解释一下你如何计算它？

如果你有一个更好的方法来计算使用递归计算Fibonacci,也欢迎.

Answer 1

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

请注意,复杂性遵循精确的公式作为序列,因为所有计算分支总是以值为1的叶结束,因此精确的(θ)复杂度可以通过Fibonacci序列本身的闭合公式精确计算

但这超出了你的问题范围,我们需要注意的是这一点

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

我们现在需要的只是求解由上定义的上界系列

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

结果是

an = 2 ^ n

所以,你得到你想要的2 ^ n的上限O.

如果你多次运行它就会得到

西格玛(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)(实际上它可以通过一个好的编译器进行优化,实现为一个循环,然后也会耗尽一个恒定的内存消耗)

Answer 2

一般来说，它背后有数学原理，斐波那契数列有解释： https: //en.wikipedia.org/wiki/Recurrence_relation

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

纸是你的朋友！

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

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

你可以画一个图：

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

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

那么你不要只说“fib(n-1)和fib(n-2)”，你首先看“fib(n-1)是否被计算在内”？如果是这样，则不进行递归，而是使用计算值。