Fibonacci算法的时间复杂度

Question

因此,我在Java中有一个递归方法来获取'n'的斐波纳契数 - 我唯一的问题是:时间复杂度是多少？我认为这是O(2 ^ n),但我可能会弄错？(我知道迭代更好,但这是一个练习)

public int fibonacciRecursive(int n)
{
    if(n == 1 || n == 2) return 1;
    else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}

Answer 1

您的递归代码具有指数运行时间。但我不认为基数是 2，而是黄金比例（大约 1.62）。但是当然 O(1.62^n) 也自动是 O(2^n)。

运行时间可以递归计算：

t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1

这与斐波那契数本身的递归定义非常相似。将+1在回归方程可能是无关大的n。SI 认为它的增长速度大约与 fibo 数一样快，并且以黄金比例为基础呈指数增长。

您可以使用记忆加速它，即缓存已经计算的结果。然后它有 O(n) 运行时，就像迭代版本一样。

您的迭代代码的运行时间为 O(n)

您有一个简单的循环，每次迭代都有 O(n) 步和恒定时间。

Answer 2

你可以用它

计算F中的O(log n)