斐波那契数列

斐波那契数

通常用F(n)表示, 形成的序列称为 斐波那契数列. 该数列由0和1开始, 后面的每一项数字都是前面两项数字的和, 也就是:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), 其中 n > 1

给你 n , 请计算 F(n)

来自 LC: 509.斐波那契数 (opens new window)

方法一: 循环 + 滚动数组

复杂度: O(n) O(1)

// function fibonacci1(n) {
//   let cur = 1
//   let prev = 1
//   for (let i = 0; i < n - 2; i++) {
//     const temp = cur
//     cur += prev
//     prev = temp
//   }
//   return cur
// }
function fibonacci1(n) {
  let cur = 1
  let prev = 1
  let ans = 1
  for (let i = 0; i < n - 2; i++) {
    prev = cur
    cur = ans
    ans = prev + cur
  }
  return ans
}

方法二: 递归

复杂度: O($2^n$) O(n)

f(n) = f(n - 1) + f(n - 2)
f(n - 1) = f(n - 2) + f(n - 3)
f(n - 2) = f(n - 3) + f(n - 4)
...
出现很多重复计算的值, 容易造成浏览器假死

function fibonacci2(n) {
  if (n <= 2) return 1
  return fibonacci2(n - 2) + fibonacci2(n - 1)
}

方法三: 递归优化

复杂度: O(n) O(n)

function fibonacci3(n, prev = 1, cur = 1) {
  if (n <= 2) return cur
  return fibonacci3(n - 1, cur, cur + prev)
}

方法四: 闭包

复杂度: O(n) O(n)

const fibonacci4 = function () {
  const arr = [0, 1]
  const f = function (n) {
    let res = arr[n]
    if (res == undefined) {
      arr[n] = f(n - 1) + f(n - 2)
      res = arr[n]
    }
    return res
  }
  return f
}()

方法五: 通项公式法

复杂度: 取决于工具函数的复杂度, 可以认定为 O(1)

$$f(n)=\frac{1}{\sqrt{5}}*\left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]$$

function fibonacci5(n) {
  return Math.floor((Math.pow(((1 + Math.sqrt(5)) / 2), n) - Math.pow(((1 - Math.sqrt(5)) / 2), n)) / Math.sqrt(5))
}

方法六: 矩阵快速幂

复杂度: O(logn) O(1)

方法一的时间复杂度是 O(n). 使用矩阵快速幂的方法可以降低时间复杂度

首先我们可以构建这样一个递推关系:

$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} * \begin{bmatrix} F(n) \\ F(n - 1) \end{bmatrix} = \begin{bmatrix} F(n) + F(n - 1) \\ F(n) \end{bmatrix} = \begin{bmatrix} F(n + 1) \\ F(n) \end{bmatrix}$$

因此:

$$\begin{bmatrix} F(n + 1) \\ F(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n * \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}$$

因此只要我们能快速计算矩阵 M 的 n 次幂, 就可以得到 F(n) 的值. 如果直接求取 $M^n$, 时间复杂度是 O(n)

可以定义矩阵乘法, 然后用快速幂算法来加速这里 $M^n$ 的求取

而计算二阶矩阵的N次幂运算, 由于二阶矩阵乘法满足结合律, 这样, 可以快速计算二阶矩阵的n次幂运算

假设A为一个二阶矩阵, 则A的幂运算满足下面的条件:

$$A^6 = A^3 ∗ A^3 = A^4 ∗ A^2 (6 = 110)$$

$$A^7 = A^3 ∗ A^3 ∗ A^1 = A^4 ∗ A^2 ∗ A^1 (7 = 111)$$

在这里, 我们可以类似地把A看做是二进制中的2, $A^7 = A^4 ∗ A^2 ∗ A^1$ 也就是说可以把矩阵的幂转换成二进制来表示 从而可以将n次幂拆解成长度为logn的二进制数来表示: 7 = 111(二进制) 这就是快速求二阶矩阵的核心方法

function fibonacci6(n) {
  if (n < 2) {
    return n;
  }
  const q = [[1, 1], [1, 0]];
  // 因为结果取得是res[0][0], 是F(n + 1) 所以只需要 n-1 次方, 取res[1][0]的话就是n次方
  const res = pow(q, n - 1);
  // res是二维数组 [[f(n + 1), f(n)], [f(n), f(n - 1)]], 再乘以[F(1), F(0)] => [1, 0]
  // 最终结果就是第一列的数据
  return res[0][0];
};
function pow(a, n) {
  // 结果矩阵 最开始的结果矩阵也可以看做是1, 因为这个矩阵和任意二阶A矩阵相乘结果都是A
  let ret = [[1, 0], [0, 1]];
  while (n > 0) {
    if ((n & 1) === 1) { // 取n的二进制的最后一位和1做与运算, 如果最后一位是1, 则进入if体内部
      ret = multiply(ret, a); // 如果在该位置n的二进制为1, 则计算矩阵乘积
    }
    n >>= 1;
    // 每右移一位 此时基础矩阵的幂都应该扩大两倍, 就是对应当前二进制位的值
    a = multiply(a, a); // 基础矩阵相乘, 相当于初始基础矩阵的幂*2
  }
  // n次幂之后的结果矩阵 就是所有二进制位1的位全部乘起来
  return ret;
}
function multiply(a, b) {
  const c = new Array(2).fill(0).map(() => new Array(2).fill(0));
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
      c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
    }
  }
  return c;
}

// 6765
console.log('fibonacci1', fibonacci1(20));
console.log('fibonacci2', fibonacci2(20));
console.log('fibonacci3', fibonacci3(20));
console.log('fibonacci4', fibonacci4(20));
console.log('fibonacci5', fibonacci5(20));
console.log('fibonacci6', fibonacci6(20));