这个递归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，该程序需要花费大量时间才能完成。

我已经通过this answer，无法理解他们是如何解决它但它看起来像

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

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

如果你不必证明它并且你只需要正确地写下来，你只需要考虑算法的行为方式和一些数字的重复次数，然后你可以尝试将它推广到任何输入n。

纸是你的朋友！

如果你的递归中你的斐波纳契值为“10”，你基本上就是说（10的finonacci是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）”？如果是这样，请使用计算出的值，而不是进行递归。