What is the time complexity of recursively solving Fibonacci sequences?

Conclusion Ox00

In my opinion, the time complexity in a strict sense should be:

$O((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$

0 x01 introduction

Recently I learned data structure, and the time complexity of Fibonacci sequence realized by recursion was briefly mentioned in the book, which was called O(2^n). I checked the origin of O(2^n) on the Internet. But in Zhihu, someone calculated the time complexity of Fibonacci sequence as O((1+52)n)O((\frac{1+\sqrt5}{2})^n)O((21+5)n). Here’s the discussion. Personal ideas, if you have any questions, please include them and point out the problems.

0x02 recursive code

– C code

#include <stdio.h>

long fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n- 1) + fib(n2 -);
}


int main(a)
{
    int i;
    for(i=0; i<10; i++)
    {
        printf("%d\n", fib(i));
    }
    return 0;
}
Copy the code

Run –

0x03 Time Complexity

– is a
$O(2^n)$

In the figure above, if you want fib of 6, you need to compute fib of 5 and fib of 4; If you want to go to fib of 5, you have to compute fib of 4 and fib of 3; And so on. If fib(2) and FIB (1) in the red box are moved to the right of the previous layer, 23=2n−3=82^3 =2 ^{n-3} = 823=2n−3=8. So as a calculation, it’s easy to get O(2n)O(2^n)O(2n).

– that two
$O((\frac{1+\sqrt5}{2})^n)$

The number of fib(1) and FIB (2) cannot be directly calculated roughly using 2n−22^{n-2}2n−2. If fib(6) is the first layer, fib(1) is the sixth layer and FIB (2) is the fifth layer. Obviously, we have the same number of fib of one and fib of three. So the total number of fib of 1 and fib of 2 is fib of 4 plus fib of 5 is equal to 3 plus 5 is equal to 8. Fib of 4 plus fib of 5 is fib of 6 is fib of n, so the total number of fib of 1 and fib of 2 is fib of n. According to the general term formula of Fibonacci series:

Fib (n) = 15 (52) (1 + n – (1-52) n) fib (n) = \ frac {1} {\ sqrt5} ((\ frac {1 + \ sqrt5} {2}) ^ n – (\ frac {1 – \ sqrt5} {2}) ^ n) fib (n) = 1 (5 (21 + 5 ) n – (21-5) n) through seeking common order equation, finally it is concluded that the time complexity is O (n) (1 + 52) O ((\ frac {1 + \ sqrt5} {2}) ^ n) O (n) (21 + 5).

– Analysis (solution)

• f(n)

  The statement frequency of fib(n) is equal to the total number of executions of FIB (1) and FIB (2) during recursion.

  Therefore, the time complexity of solving the recursive algorithm is equivalent to solving the recursive equation.

  The Fibonacci sequence

  F (n)=f(n-1)+f(n-2) for n>=2

  When n equals 0 or n equals 1, f of n equals 1

  Recursive equation solution, that is, to find the general term of the Fibonacci sequence formula.

  F (n) = 15 (52) (1 + n – (1-52) n) (n) = f \ frac {1} {\ sqrt5} ((\ frac {1 + \ sqrt5} {2}) ^ n – (\ frac {1 – \ sqrt5} {2}) ^ n) (n) = 5 f 1 ((21 + 5) n – (21-5) n)

• "O"

  Find functions of the same order as f sub n. In the algorithm, the same order means that when n->∞, the ratio of two functions results in a non-zero constant, then the two functions are said to be of the same order.

  • If the time is O(2n)O(2^n)O(2n). The limit of comparison is 0

  • If the time complexity is O (n) (1 + 52) O ((\ frac {1 + \ sqrt5} {2}) ^ n) O (n) (21 + 5). The limit of comparison is 15\frac{1}{\sqrt5} 51

• Ret: The leading function of the Fibonacci sequence is of the same order as (1+52)n(\frac{1+\sqrt5}{2})^n(21+5)n.

– Another way of thinking

If the fib(n) execution time is T(n), the FIB (n-1) execution time is T(n-1), and the FIB (n-2) execution time is T(n-2). Statement if (n = = 0 | | n = = 1) return 1; Is O(1). The time of the if statement relative to the return statement is negligible.

So T = T (n) (n – 1) + T (n) (n – 2) T = T (n – 1) + T (n) (n – 2) T = T (n – 1) + T (n – 2).

When n=1 or n=2, the FIB function returns 1, and the execution time is O(1)O(1)O(1).

In conclusion:

The recursive equation is solved, and the execution time of FIB (n) is:

$T(n)=\frac{1}{\sqrt5}((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$

When n – > up reduction again, you can get the time complexity is O (n) (1 + 52) O ((\ frac {1 + \ sqrt5} {2}) ^ n) O (n) (21 + 5).

0x04 Personal thoughts

The mathematical symbol “O” is strictly defined as:

If T(n) and f(n) are two functions defined on the set of positive integers, then T(n)=O(f(n)) means that there are positive constants C and n0 such that 0<=T(n)<=Cf(n) for n>=n0.

So, from the strict sense, O (n) (1 + 52) O ((\ frac {1 + \ sqrt5} {2}) ^ n) O (n) (21 + 5) is also wrong. F (n) = 15 (52) (1 + n – (1-52) n) (n) = f \ frac {1} {\ sqrt5} ((\ frac {1 + \ sqrt5} {2}) ^ n – (\ frac {1 – \ sqrt5} {2}) ^ n) (n) = 5 f 1 ((21 + 5) n – (21-5) n)

Where (1−52)n(\frac{1-\sqrt5}{2})^n(21−5)n is positive and negative related to the parity of n, so f(n) is fluctuating and C cannot exist, such that 0<=T(n)<=Cf(n) when n>=n0.

To sum up, strictly speaking, time complexity should be:

$O((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n)$

0 x05 summary

By analysis (not strictly), the time complexity of the recursive form of the Fibonacci sequence should be O((1+52)n) O((\frac{1+\sqrt5}{2})^n)O((21+5)n).

What about O(2n)O(2 to the n)O(2n)?

1. First, the result of fib(6) calculated by 2(6−3)2^{(6-3)}2(6−3) is the same as that calculated by fib(5)+fib(4)fib(5)+fib(4)fib(5)+fib(4) fib(5)+fib(4). When n is not 6, it’s obviously not the same, the equation is different.

2. What both time complexities have in common is that they are exponential. Because O(2n)O(2^n)O(2n) is a representation of the exponential order, it is possible to use O(2n)O(2^n)O(2n) as the time complexity of the recursive solution of the Fibonacci sequence just to show that it is exponential order.

3. The general exponential algorithm is not considered to use, so it is ok to know that this is an exponential time complexity, and it is not necessary to study what its time complexity is. And (asymptotically) time complexity is not the real time for the machine to execute the algorithm.

Two time-complexity function graphs