Computational complexity of Fibonacci Sequence

I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

What is the computational complexity of the Fibonacci sequence and how is it calculated?

---

You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together ( O(1) ).

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2 n ) . You can then prove your conjecture by induction.

Base: n = 1 is obvious

Assume T(n-1) = O(2 n-1 ) , therefore

T(n) = T(n-1) + T(n-2) + O(1) which is equal to

T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )

However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are defined as

f(n) = f(n-1) + f(n-2) .

The leaves of the recursion tree will always return 1. The value of Fib(n) is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, T(n) is equal to Fib(n) x O(1) . Consequently, the tight bound for this function is the Fibonacci sequence itself (~ θ(1.6 n ) ). You can find out this tight bound by using generating functions as I'd mentioned above.

---

Just ask yourself how many statements need to execute for F(n) to complete.

For F(1) , the answer is 1 (the first part of the conditional).

For F(n) , the answer is F(n-1) + F(n-2) .

So what function satisfies these rules? Try an (a > 1):

an == a(n-1) + a(n-2)

Divide through by a(n-2):

a2 == a + 1

Solve for a and you get (1+sqrt(5))/2 = 1.6180339887 , otherwise known as the golden ratio.

So it takes exponential time.

---

There's a very nice discussion of this specific problem over at MIT. On page 5, they make the point that, if you assume that an addition takes one computational unit, the time required to compute Fib(N) is very closely related to the result of Fib(N).

As a result, you can skip directly to the very close approximation of the Fibonacci series:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

and say, therefore, that the worst case performance of the naive algorithm is

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you'd like more information.

链接地址: http://www.djcxy.com/p/6790.html

上一篇: Θ（n）和O（n）之间的区别是什么？

下一篇: 斐波那契数列的计算复杂性