計算斐波那契數列的時間複雜度解析

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

四、小結

以上是計算斐波那契數列的三種方法，分別是遞歸、循環和使用矩陣。遞歸方法雖然簡單直觀，但時間複雜度很高，效率低下。循環和矩陣在時間複雜度上有很大的優勢，可以快速地計算斐波那契數列。