Fibonacci numbers

What are Fibonacci numbers? The sequence of the first1And the first2Items for1From the first3You start with terms that are equal to the sum of the previous two terms1,1,2,3,5,8,13,21,34And... N Find the NTH term of the Fibonacci sequenceCopy the code
  • 1. Primary solution
/* 1. The first and second entries in the sequence are deterministic, so return 1 if n is 1 or 2. The third term in the sequence starts as the sum of the first two terms, so for example, if n is 5, the fifth term will be the sum of the fourth and third terms, and the fourth term will be the sum of the third and second terms, and so on */
function fib(n) {
    if (n===1 || n===2) {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}
Copy the code

  • Time complexity: It can be seen from the figure that the fifth term can be decomposed into the sum of the fourth and third terms, and so on. Each parent term is split into two children. And the height of the tree is n minus 1, so the time is complicated here O of n is 2 to the n
  • Space complexity: if the fifth term is required here, then the implementation of the stack should start from the fourth term -> the third term -> the second term, and then reach the exit after reaching the second term, so here the depth of the stack is n-1, that is, the space complexity O(n) is N
We can see that as n increases, the time it takes to compute the NTH term increases exponentially and explosively, which is hard to acceptCopy the code
  • 2. Fibonacci sequence solution with memo

We can see that in order to compute term 5, we need to compute term 4 once and term 3 twice. We can imagine that if we were looking for the 9,999th term, we would have to do a lot of calculations for the third term, but are these calculations really necessary? It is these repeated calculations that lead to the explosive growth of the algorithm’s time complexity. So if we know the problem, the solution is also very simple, as long as we can cache the results of previous calculations

const fib = (function () {
    const memo = {
        1: 1.2: 1};return function _getFib(n){
        if (memo[n]) {
            return memo[n];
        }
        const res = _getFib(n-1) + _getFib(n-2);
        memo[n] = res;
        return memo[n]
    }
})()
Copy the code

  • Time complexity: can be seen from figure 2 if required item 5, we no longer need the fission continuously, but turned into a straight line, because every time the fission we can find the corresponding values in the cache, directly into the time complexity O (n), before has not been optimized and the solution to the essential difference between.
  • Space complexity: the space complexity is still the same, of course, there are ways to reduce space complexity, need dynamic programming.

We can see that in order to solve for the NTH term, we have to solve for the n-1 and n-2 terms, and so on. Then the NTH term is reduced to a subproblem of the n-1 and n-2 terms, and the n-1 solution is the same as the NTH term. So the data structure for the NTH term is exactly the same as the data structure for the n-1 term. That’s why we can break down the NTH term to the n-1 term. This is also the essence of recursion, the decomposition of a parent problem into sub-problems of the same data structure.