斐波那契数列是一个数列，其中每个数都是前两个数的和，第一个数和第二个数都是1。斐波那契数列的前几项为：1,1,2,3,5,8,13,21,34，…。计算斐波那契数列常用的方法是递归和循环，不同的方法会导致不同的时间复杂度。
一、递归计算斐波那契数列
递归计算斐波那契数列最直观的方法是使用递归函数：
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10)); // 输出89
但是，递归计算斐波那契数列的时间复杂度是指数级别的，因为这个函数会重复计算很多相同的值。
以计算fibonacci(5)为例，可以画出递归树：
fibonacci(5)
/ \
fibonacci(4) fibonacci(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \ / \ / \
f(2) f(1) f(1) f(0) f(1)
/ \
f(1) f(0)
可以看到，递归函数重复计算了很多的值，如f(2)被计算了3次，f(1)被计算了5次。递归函数的时间复杂度为O(2^n)。
二、循环计算斐波那契数列
循环计算斐波那契数列是一种更高效的方法。我们可以用循环计算来避免重复计算，从而提高效率。
以下是循环计算斐波那契数列的例子：
function fibonacci(n) {
if (n <= 1) {
return 1;
}
let first = 1, second = 1;
for (let i = 2; i <= n; i++) {
let temp = second;
second = first + second;
first = temp;
}
return second;
}
console.log(fibonacci(10)); // 输出89
这个算法的时间复杂度为O(n)，因为只需要迭代n次即可计算出斐波那契数列的第n个值。
三、使用矩阵计算斐波那契数列
另外一个高效的斐波那契数列计算方法是使用矩阵。
斐波那契数列可以表示为如下的矩阵乘积形式：
[1, 1] [f(n-1), f(n-2)] [f(n), f(n-1)]
= *
[1, 0] [f(n-2), f(n-3)] [f(n-1), f(n-2)]
因此，我们可以使用矩阵的快速幂算法来计算斐波那契数列。这个算法的时间复杂度为O(log n)。
function pow(matrix, n) {
let result = [[1, 0], [0, 1]];
while (n > 0) {
if (n & 1) {
result = multiply(result, matrix);
}
matrix = multiply(matrix, matrix);
n >>= 1;
}
return result;
}
function multiply(matrix1, matrix2) {
let result = [[0, 0], [0, 0]];
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
for (let k = 0; k < 2; k++) {
result[i][j] += matrix1[i][k] * matrix2[k][j];
}
}
}
return result;
}
function fibonacci(n) {
if (n <= 1) {
return 1;
}
let matrix = [[1, 1], [1, 0]];
let result = pow(matrix, n - 1);
return result[0][0] + result[0][1];
}
console.log(fibonacci(10)); // 输出89
四、小结
以上是计算斐波那契数列的三种方法，分别是递归、循环和使用矩阵。递归方法虽然简单直观，但时间复杂度很高，效率低下。循环和矩阵在时间复杂度上有很大的优势，可以快速地计算斐波那契数列。
原创文章，作者：AMKIQ，如若转载，请注明出处：https://www.506064.com/n/374947.html
微信扫一扫 
支付宝扫一扫 