前言
斐波那契数列是指每一项均为前两项之和的数列，标准的斐波那契数列为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]
}
以上就是斐波那契数列常用的解法，后两种代码复杂度同为O(log(n))，矩阵解法在代码实现上要麻烦些，可读性略低，具体使用看各位的喜好