算法已经是程序员面试中必不可少的一个考点，而在算法中，有那么一个问题是经常被问的，那就是斐波拉契数列。斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入

斐波拉契这个问题非常有意思，它看似简单，其实里面有很多的门道，从最初级的程序员到算法高手，都能写出来答案，每个人都觉得自己写的对，但是其实很少有人能写出最完美的答案…

定义

斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89... 这个数列从第3项开始，每一项都等于前两项之和。

递归

基于每一项等于前两项之和的思想，斐波那契数列很容易看出“递归”，那么，我们只需要在非终止条件下无脑递归即可。

• 时间复杂度 O(n^2)
• 间复杂度 O(n)，不论总递归次数为多少，总递归深度为 n

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

递归的解法是最简单。在面试中肯定不是面试官想要的答案。因为时间复杂度是 O(n^2)。接着我们看看第二种方式，迭代。

迭代

let fibnacci = n => {
  if (n === 0) return 0;
  let a1 = 0, a2 = 1;
  for (let i = 1; i < n; i++) {
    [a1, a2] = [a2, a1 + a2];
  }
  return a2;
}

• 时间复杂度 O(n)
• 间复杂度 O(n)

迭代这种方法在面试中，只要你能写出来，基本已经满足面试官的要求了。当然还有更好的算法吗？有的。

通用公式

使用生成函数求斐波那契的通项公式：

我们求出了斐波那契数列的生成函数

接下来通过生成函数求原始数列

let fibnacci = n => (Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5);

注意：由于浮点数的原因我们还需要对结果进行 Math.round 处理。

let fibnacci = n => Math.round((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));

• 时间复杂度不好衡量（幂运算的原因），不是 O(1)，但是肯定小于 O（n）
• 空间复杂度O(1)

这个通用公式写出来，我感觉已经有 50% 的面试官已经看不懂了。那还有更好的算法吗？有的。

矩阵快速幂

综合矩阵运算和快速幂运算，代码如下：

let matrix22_mul = (x, y) => [  [x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1]],
  [x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]
];

let matrix22_pow = (x, n) => {
  var r = [[1,0], [0,1]];
  var v = x;
  while(n) {
    if (n % 2 === 1) {
      r = matrix22_mul(r, v);
      n -= 1;
    }
    v =  matrix22_mul(v, v);
    n = n / 2;
  }
  return r;
}

let fibnacci = n => n <= 0 ? 0 : matrix22_mul([[0, 1], [0, 0]], matrix22_pow([[0, 1], [1, 1]], n - 1))[0][1];

• 时间复杂度O(log⁡n)
• 空间复杂度O(1)

如果你在面试中，用矩阵快速幂来求解斐波拉契数列，我想 80% 的面试官看不懂你这解法。

不过真的在面试中，大家不要轻易冒险去写这个算法，原因是风险比较大，如果你真的懂了，你可以写。如果你只是背了代码，不理解？面试官让你解释一下，你就 GG 了。

小结

在面试中，个人感觉能写出“递归”和“迭代”这两种斐波拉契数列的方式就已经能满足要求了。后面两种方式如果你真的理解了就可以在面试中装逼一下，如果没有完全理解，就不要去写了。万一哪个面试官真的头铁问你原理了，那得不偿失了。所以量力而行。

参考

• leetcode.cn/problems/fi…
• letmefly.blog.csdn.net/article/det…
• baike.baidu.com/item/%E6%96…