计算斐波那契数列的时间复杂度解析

斐波那契数列是一个数列，其中每个数都是前两个数的和，第一个数和第二个数都是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

四、小结

以上是计算斐波那契数列的三种方法，分别是递归、循环和使用矩阵。递归方法虽然简单直观，但时间复杂度很高，效率低下。循环和矩阵在时间复杂度上有很大的优势，可以快速地计算斐波那契数列。