“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

I’m sure you’ve all heard of the Fibonacci sequence, and if you feel a little strange about the Fibonacci sequence, you probably haven’t studied the algorithm. When we talk about recursion, we always use the Fibonacci sequence, because it’s so classical, and today we’re going to go into the Fibonacci sequence.

What are Fibonacci numbers?

Mathematician Leonardo Fibonacci used rabbit breeding as an example to introduce it, so it is also called “rabbit sequence”. At that time, he proposed that if a pair of newly born rabbits could grow into big rabbits in one month, and give birth to a pair of young rabbits in another month, and give birth to a pair of young rabbits every month after that, no death occurred in a year, he asked: How many pairs of newly born rabbits could be bred into in a year?

The formation of the sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Mathematically, the Fibonacci sequence is defined recursively as follows: F(0)=0, F(1)=1, F(n)=F(n-1) + F(n-2) (n ≥ 2, n ∈ N*)

Solution one: recursion

Time complexity: O(2 2N)

Space complexity: O(1)

The Fibonacci sequence is made for recursion, and we can see from the problem that the rule is that the last number is the sum of the first two numbers, its boundary is F(0)=0, F(1)=1, and its recursive call is F(n-1) + F(n-2).

Schematic diagram:

The code is as follows:

public int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}
Copy the code

Solution 2: Memorized search (memo algorithm)

Time complexity: O(n)

Space complexity: O(n)

As can be seen from the above recursion principle picture, a large number of intermediate data are duplicated during recursion. We cache these repeated intermediate values through Map, so that we only need to recurse once for the same value to get the solution, which can greatly improve the efficiency of recursion. This is called mnemonic search.

This algorithm, which is a classic space for time, has n numbers and we need to cache n values.

After optimization, the amount of computation we need is greatly increased. The answer can be obtained from the following figure

The code is as follows:

public int fibonacci(int n) {
    Map<Integer,Integer> cache = new HashMap<>();
    if (n < 2) {
        return n;
    }
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    int value = fibonacci(n - 1) + fibonacci(n - 2);
    cache.put(n,value);
    return value;
}
Copy the code

Solution three: dynamic programming

Time complexity: O(n)

Space complexity: O(1)

Recursion is a top-down process, so can we solve from the bottom up?

From low to high means that we have F(0)=0, F(1)=1, F(2)… F(n) is that better? Apparently it can.

Because Fibonacci numbers have this recursive relationship, we can use dynamic programming to solve. The state transition equation of dynamic programming is the recursive relation mentioned above, and the boundary conditions are F(0) and F(1).

According to the state transition equations and boundary conditions of dynamic programming, we can obtain an implementation of O(n) in both time complexity and space complexity. Since F(n) is only related to F(n−1) and F(n−2), we can use the idea of rolling arrays to optimize the space complexity to O(1).

The code is as follows:

public int fibonacci(int n) { if (n < 2) { return n; } int p = 0, q = 0, r = 1; for (int i = 2; i <= n; ++i) { p = q; q = r; r = p + q; } return r; }}Copy the code

Solution 4: Fast powers of matrices

Time complexity: O(logn)

Space complexity: O(1)

The time complexity of dynamic programming is O(n). We can reduce the time complexity by using the matrix fast power method.

First build the recursive relationship:

get

make

public int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    int[][] q = {{1, 1}, {1, 0}};
    int[][] res = pow(q, n - 1);
    return res[0][0];
}
​
public int[][] pow(int[][] a, int n) {
    int[][] ret = {{1, 0}, {0, 1}};
    while (n > 0) {
        if ((n & 1) == 1) {
                ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}
​
public int[][] multiply(int[][] a, int[][] b) {
    int[][] c = new int[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
        }
    }
    return c;
}
Copy the code

Solution 5: general term formula

Fibonacci number F(n) is a homogeneous linear recursion, according to the recursion equation F(n)=F(n-1)+F(n-2),

The characteristic equation can be written as x²=x+1

The time and space complexity of poW functions in the code is related to the instruction set supported by the CPU and will not be analyzed here.

The code is as follows:

public int fibonacci(int n) {
    double sqrt5 = Math.sqrt(5);
    double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
    return (int) Math.round(fibN / sqrt5);
}
Copy the code

Description:

Solution 4 and Solution 5 were found in the solution of LeetCode problem. The efficiency is really high, but what I see is ambiguous. These are related knowledge points of higher mathematics, and if you are interested, you can further study, the end of the algorithm is still mathematics!!

The first three solutions should be mastered by all of us.