time-complexity - 这个递归斐波那契的 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，该程序需要很多时间才能完成。

我经历过 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)(事实上，它可以由一个好的编译器优化以实现为循环，然后也会消耗恒定的内存消耗)