Fibonacci

Fibonacci 数列

介绍

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

通过观察,可以发现 F(n) = F(n-1) + F(n-2);当 n 趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割 0.618

算法

递归

1
2
3
4
5
const fibonacci = (n) => {
if (n <= 1) return n;

return fibonacci(n - 1) + fibonacci(n - 2);
}

虽然简洁,但时间复杂度近似 O(2^n);而且 n 越大,所需的空间越大,函数调用层级越深,可能导致栈溢出。还有一点,就是存在重复计算。

迭代

采用迭代循环计算斐波那契数列,时间复杂度为 O(n),空间复杂度为 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
const fibonacci = (n) => {
if (n <= 1) return n;

let prev = 0, // n - 2
last = 1; // n - 1

for (let i = 2; i <= n; i++) {
[prev, last] = [last, prev + last];
}

return last;
}

通项公式

斐波那契数列有个通项公式:

这个公式可以通过构造等比数列或者特征方程法等方法求出,也可以利用数学归纳法进行证明。具体的推导过程可参考 斐波那契数列的通项公式

1
2
3
4
5
const fibonacci = (n) => {
if (n <= 1) return n;

return Math.ceil((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));
}

这种方式涉及到浮点数的计算,容易会出现误差;随着 n 增大,误差也会不断增大,一般不使用这种方式计算。

矩阵

公式:

证明过程:

代码

coding…