O递归斐波那契的时间复杂度？

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

这是该计划：

#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）

我也许完全错了，但我想要的只是：

什么是这个完整程序的时间复杂性，简单地解释你如何计算它？

如果你有更好的方法来计算斐波纳契使用递归，也是受欢迎的。

---

（纤维（n））= c（纤维（n-1））+ c（纤维（n-2））+ O（1）

请注意，复杂性遵循系列中的精确公式，因为所有计算分支始终以叶子值1结束，因此精确（θ）复杂性可以通过斐波那契数列本身的封闭公式准确计算

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

c（fibo（n））<2 * c（fibo（n-1））

我们现在需要的是解决由上面定义的系列上限

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

结果是

an = 2 ^ n

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

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

sigma（c（fib（n）））从1到TERMS = 0（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）（事实上，它可以通过一个好的编译器进行优化，以便作为一个循环来实现，并且会消耗一个固定的内存）

---

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

如果你不必证明它，你只需要正确写下它，那么你就必须考虑算法的行为方式以及对于某个数字会有多少次重复，然后你可以尝试将它推广到任何输入n 。

纸是你的朋友！

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

链接地址: http://www.djcxy.com/p/39919.html

上一篇: O time complexity for this recursive Fibonacci?

下一篇: Most efficient way to calculate Fibonacci sequence in Javascript