本质

假设：一对成年兔子每年生一对小兔，小兔一年后成年。
提问：一开始有一对小兔，N年后共有多少只兔子？

image.png
1 1 2 3 5 8 13 …
image.png

假设：上一个N级台阶的楼梯，每次只能走一格或者两格。
提问：总共有多少种走法？

满二叉树？

o(n*n)

  1. let fibnacci = n => n <= 0 ? 0 : (n = 1 ? 1 : fibnacci(n-2) + fibnacci(n-1)

o(n)

递归变迭代，动态规划

  1. let fibnacci = n => {
  2.     if(n == 0) return 0;
  3.   let a1 = 0, a2 = 1;
  4.   for (let i = 1; i < n; i ++) {
  5.     [a1, a2] = [a2, a1 + a2];
  6.   }
  7.   return a2;
  8. }

o(log(n))

通项公式
image.png

  1. let fibnacci = n => (Math.pow((1 + Math.sqrt(5))/2, n)-Math.pow((1-Math.sqrt(5))/2, n)/Math.sqrt(5)
  1. let pow = (x, n) => {
  2.   let r = 1;
  3.   let v = x;
  4.   while (n) {
  5.     if (n % 2 == 1) {
  6.       r *= v;
  7.       n -= 1;
  8.     }
  9.     v = v * v;
  10.     n = n / 2;
  11.   }
  12.   return r;
  13. }

o(n)

矩阵法