Fibonacci算法的时间复杂度 [英] Time Complexity of Fibonacci Algorithm

问题描述

所以，我在Java中有一个递归方法来获得'第n个斐波纳契数 - 我唯一的问题是：时间复杂度是多少？我认为这是O（2 ^ n），但我可能弄错了？ （我知道迭代更好，但这是一个练习）

So, i've got a recursive method in Java for getting the 'n'th fibonacci number - The only question i have, is: what's the time complexity? I think it's O(2^n), but i may be mistaken? (I know that iterative is way better, but it's an exercise)

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

推荐答案

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

Your recursive code has exponential runtime. But I don't think the base is 2, but probably the golden ratio (about 1.62). But of course O(1.62^n) is automatically O(2^n) too.

运行时可以递归计算：

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

这与斐波纳契数字本身的递归定义非常相似。递归方程中的 +1 可能与大n无关。 SI相信它的增长速度大约与fibo数一样快，并且随着黄金比率的增长呈指数增长。

This is very similar to the recursive definition of the fibonacci numbers themselves. The +1 in the recursive equation is probably irrelevant for large n. S I believe that it grows approximately as fast as the fibo numbers, and those grow exponentially with the golden ratio as base.

你可以使用memoization来加速它，即已经缓存计算结果。然后它就像迭代版本一样具有O（n）运行时。

You can speed it up using memoization, i.e. caching already calculated results. Then it has O(n) runtime just like the iterative version.

你的迭代代码的运行时间为O（n ）

Your iterative code has a runtime of O(n)

你有一个简单的循环，每次迭代都有O（n）步和恒定时间。

You have a simple loop with O(n) steps and constant time for each iteration.

这篇关于Fibonacci算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！