The Fibonacci sequence goes from O(2^n) to O(1).

Definition of Fibonacci sequence

There are n stairs and you can climb one or two steps at a time. How many ways can you climb up n stairs? The problem is different from the Fibonacci sequence except for the initial conditions.

1. The recursive method

function fib1(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fib1(n - 1) + fib1(n - 2)}Copy the code

Recursion is easy to understand, but time is too complicated. So let’s say FIB of 10, fib of 10, fib of 10.

$fib(10)=fib(9)+fib(8)$

$fib(9)=fib(8)+fib(7)$

$fib(8)=fib(7)+fib(6)$

It can be seen from the above three formulas that FIB (8), FIB (7) FIB (8), FIB (7) FIB (8), fib(7) FIB (8), fib(7) FIB (8), fib(7)fib(8) are computed twice. When n is large, more subitems are computed multiple times, resulting in computational redundancy and time complexity as high as O(2n)O(2^n)O(2n).

2. Memo recursion

Since found fib (8), fib (7) fib (8), fib (7) fib (8), fib (7) be repeated computation, so we use the extra space for storage, their results if fib (8) fib (8) fib (8) has not been calculated, are calculated, and store it, The next time you encounter fib(8)fib(8)fib(8) fib(8), you get the fib(8) directly from the storage space, which saves a lot of time.

function fib2(n) {
   let memory = new Array(n + 1).fill(0);
   const memo = (memory, k) = > {
      if (k === 1 || k === 2) return 1;
      if (memory[k]) return memory[k];
      memory[k] = memo(memory, k - 1) + memo(memory, k - 2);
      return memory[k];
   };
   return memo(memory, n);
}
Copy the code

Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).

3. Bottom-up memos

Recursive method in computing fib fib (n) (n) fib (n), from the large number of calculations, until the fib (2), fib (1) fib (2), fib (1) fib (2), fib (1), since can from big to small, so can also grew up to fill the memo array.

function fib3(n) {
   let memory = new Array(n + 1).fill(1);
   for (let i = 2; i < n; i++) {
      memory[i] = memory[i - 1] + memory[i - 2];
   }
   return memory[n - 1];
}
Copy the code

Here the memory [0] = > fib2 (1), the memory [I] = > fib (I + 1) memory [0] = > fib2 (1), Memory [I] = > fib (I + 1) memory [0] = > fib2 (1), the memory [I] = > fib (I + 1), so the fib (n) = > memory [n – 1) fib (n) = > Memory [n – 1) fib (n) = > memory [n – 1). Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).

4. Throw away the memo

You don’t really need extra space, remember the first two values with a variable, the current value is equal to the sum of the first two values, and then update the first two values, which reduces the space complexity to O(1)O(1)O(1).

function fib4(n) {
   if(n === 1 || n === 2) return 1;
   let pre = 1, cur = 1, sum = 2;
   for(let i = 3; i <= n; i++) {
       sum = pre + cur;
       pre = cur;
       cur = sum
   }
   return cur;
}
Copy the code

5. General term formula method

Dream back to high school! (If you’re in high school, forget it.)

$Known: a_1 = 1, a_ a_2 = 1, 2} {n + = a_ + a_ (n + 1} {n} (n > = 1)$

$A_ {n+2} -ta_ {n+1} = k(a_{n+1}-ta_n)$

$=>a_{n+2}=(t+k)a_{n+1}-tka_n$

$T +k=1, tk=-1$

$=>t(1-t)=-1=>t^2-t-1=0$

$=>t_1=\frac{1+\sqrt{5}}{2},k_1=\frac{1-\sqrt{5}}{2}; t_2=\frac{1-\sqrt{5}}{2},k_2=\frac{1+\sqrt{5}}{2}$

$Make b_n = a_ {n + 1} – ta_n, is b_ {n + 1} = a_ {n + 2} – ta_} {n + 1, b_1 = a_2 – ta_1 = 1 – t = k$

$B_ {n+1} = kb_n=k^nb_1=k^{n+1}$

$=>b_n=k^n=>a_{n+1}-ta_n=k^n$

$= >$

$A_ (n + 1} – t_1a_n = k_1 ^ n \ cdots (1)$

$A_ (n + 1} – t_2a_n = k_2 ^ n \ cdots (2)$

$(1) – (2) = > (t_2 – t_1) a_n = k_1 ^ n – k_2 ^ n$

$a_n=\frac{k_1^n-k_2^n}{t_2-t_1}=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}$

function fib5(n) {
   let sqrt5 = Math.sqrt(5);
   return (Math.pow(1 + sqrt5, n) - Math.pow(1 - sqrt5, n)) / (sqrt5 * Math.pow(2, n));
}
Copy the code

We won’t deal with this for the moment because we may have to calculate decimals for accuracy reasons.

6. Time consuming tests

This section mainly compares fib4 and FIB5 time. Although FIB5 time complexity is O(1)O(1)O(1), it also needs to be calculated. Test code:

const test = [
   1000000.10000000.100000000.1000000000
];
for (let i = 0; i < test.length; i++) {
     let n = test[i];
     t1 = new Date().getTime();
     fib4(n);
     t2 = new Date().getTime();
     fib5(n);
     t3 = new Date().getTime();
     console.log("fib4", t2 - t1);
     console.log("fib5", t3 - t2);
}
Copy the code

Test results Screenshot

	1000000	10000000	10000000	1000000000
fib4	19	68	172	1607
fib5	0	0	0	0

O(1)O(1)O(1) O(1)