所以,我在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算法的时间复杂度
发布评论