Time Complexity of Fibonacci Algorithm [duplicate]

问题:

This question already has an answer here:

• Computational complexity of Fibonacci Sequence 12 answers

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);
}

回答1:

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.

The runtime can be calculated recursively:

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

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.

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

---

Your iterative code has a runtime of O(n)

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

回答2:

You can use this

to calculate Fn in O(log n)

回答3:

Each function call does exactly one addition, or returns 1. The base cases only return the value one, so the total number of additions is fib(n)-1. The total number of function calls is therefore 2*fib(n)-1, so the time complexity is Θ(fib(N)) = Θ(phi^N), which is bounded by O(2^N).

回答4:

O(2^n)? I see only O(n) here.

I wonder why you'd continue to calculate and re-calculate these? Wouldn't caching the ones you have be a good idea, as long as the memory requirements didn't become too odious?

Since they aren't changing, I'd generate a table and do lookups if speed mattered to me.

回答5:

It's easy to see (and to prove by induction) that the total number of calls to fibonacciRecursive is exactly equal to the final value returned. That is indeed exponential in the input number.