这个递归斐波那契的Big-O时间复杂度？

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

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

我看了这个答案，不明白他们是怎么解决的，但看起来

fibo（int n）的时间复杂度为O（2^n）

我可能完全错了，但我只想：

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

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

Answer 1

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

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

我们可以通过使用记忆的动态规划方法大大改进这一点，该方法基本上是将重复子问题（例如示例中的fib（2）或fib（3））存储在某种查找表中。这将时间复杂度降低到O（n）。

Answer 2

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

如果你不需要证明它，只需要正确地写下来，你只需要考虑算法的行为，以及一些数字会有多少次重复，然后你可以尝试将其推广到任何输入。

纸是你的朋友！

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

然后你们说斐波那契9，它是斐波那契8，斐波那契7等等。

你可以画一个图表：

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

如何使其在递归alghoritm中有效？从图中可以看出，fib（7）求解了三次。所以你必须记住fib（n），一旦你计算了它。它可以是全局变量，也可以通过递归调用传递对对象的引用。

然后你不只是说“fib（n-1）和fib（n-2）”，你首先看“fib（n-1）被计算了吗？”？如果是这样，则使用计算值而不是递归。

Answer 3

c（fibo（n））=c（fibo（n-1））c（fibo（n-2））O（1）

注意，由于所有计算分支始终以值为1的叶结束，因此复杂度遵循级数的精确公式，因此精确（θ）复杂度可以通过斐波那契级数本身的闭合公式精确计算

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

c（fibo（n））

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

an=2*an-1（a1,2=1）

结果在

an=2^n

因此，得到了想要的2^n的上界O。

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

σ（c（fib（n）））从1到项=O（2^（项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）（事实上，它可以由一个好的编译器优化，以实现为循环，然后还将消耗恒定的内存消耗）