前言

斐波那契数列是指每一项均为前两项之和的数列,标准的斐波那契数列为0,1,1,2,3,5,8,13,21,34,55,89,144,233 …

斐波那契数列问题有多种表述形式(马甲),常见的有以下几种

  • 兔子繁殖问题:农场里起初有一对兔子,每年繁殖一对小兔,小兔一年后成年,问n年后农场里一共有多少对兔子?
  • 跳台阶问题:小和尚从山脚下往山上跳台阶,每次可以跳一级或者两级台阶,问要跳到n级台阶,一共有多少种跳法?
  • 矩形覆盖问题:用n个2 * 1的小矩形无重叠地完全覆盖一个2 * n的大矩形,总共有多少种方法?

下面就来由简入深,一一讲解每种解法的实现及复杂度

解法一:递归实现

/**
 * 递归实现,复杂度O(2^n)
 */
const f1 = function(n) {
  if (n <= 0) {
    return 0
  } else if (n == 1) {
    return 1
  } else {
    return f1(n - 2) + f1(n - 1)
  }
}

这种方式代码看起来很简洁优美,但实际上却是效率最低,复杂度最高的方法,包含了许多的重复计算,代码复杂度是O(2^n)。

理论上计算斐波那契数列第n项只需要n次运算即可得到,于是我们有了下面的第二种解法:

解法二:迭代实现

/**
 * 迭代实现,复杂度O(n)
 */
const f2 = function(n) {
  if (n <= 0) return 0
  let a = 0
  let b = 1
  for (let i = 1; i < n; i++) {
    b = a + b
    a = b - a
  }
  return b
}

到这里,我们去除了不必要的重复计算,将代码复杂度减少到了O(n)。

单纯从代码层面似乎没有太多可以优化的空间了,接下来让我们转变思维,从数学角度来思考一下:

解法三:通项公式实现

其实前人已经为我们铺好了路,斐波那契数列已经被证实存在以下通项公式(具体推导过程还是挺复杂的,在这里不做介绍了,有兴趣的同学自己上网查阅相关资料)

这里不给出代码了,因为js处理浮点数本身就存在问题,而且处理大量数据的话也很耗性能,虽然是O(log(n)),重点在下个方法:

解法四:矩阵实现

回到第二步的迭代实现,其实每一次迭代都是在做将a,b转化为b,a+b的计算,如果我们将其转化为矩阵,就有了以下公式:

将斐波那契数列代入这个公式,其最初的两项为a=0,b=1,我们可以得到

const f4 = function (n) {
  // 乘法
  const mul = function (x,y) {
    let ans = [[],[]]
    ans[0][0] = x[0][0] * y[0][0] + x[0][1] * y[1][0]
    ans[0][1] = x[0][0] * y[0][1] + x[0][1] * y[1][1]
    ans[1][0] = x[1][0] * y[0][0] + x[1][1] * y[1][0]
    ans[1][1] = x[1][0] * y[0][1] + x[1][1] * y[1][1]
    return ans
  }
  const fpow = function (x, n) {
    let ans = [[1, 0],[0, 1]]
    let y = x
    while(n) {
      if(n % 2){
        ans = mul(ans, y)
        n--
      }
      y = mul(y, y)
      n /= 2
    }
    return ans
  }
  if(n < 1) return 0
  let x = [[0, 1],[0, 0]]
  let y = [[0, 1],[1, 1]]
  return mul(x, fpow(y,n-1))[0][1]
}

console.log(f4(3))
console.log(f4(4))
console.log(f4(5))
console.log(f4(6))
console.log(f4(7))
console.log(f4(8))
console.log(f4(9))

以上就是斐波那契数列常用的解法,后两种代码复杂度同为O(log(n)),矩阵解法在代码实现上要麻烦些,可读性略低,具体使用看各位的喜好

参考链接

斐波那契数列的N种解法