这个递归斐波那契的大 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);
    }
}

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

我已经完成 this answer 并且无法理解他们是如何解决的，但它看起来像

Time complexity for fibo(int n) is O(2^n)

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

这个完整程序的时间复杂度是多少，请简要说明您是如何计算的？

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

Answer 1

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)

结果

an = 2^n

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

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

sigma(c(fib(n))) from 1 to 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 等等

你可以画个图：

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

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

那你不就说"fib(n-1) and fib(n-2)"，你先看看"is fib(n-1) counted"？如果是这样，请使用计算值而不是递归。

Answer 3

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

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

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

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

Big-O time complexity for this recursive Fibonacci?

time-complexity

big-o

complexity-theory

asymptotic-complexity

code-complexity