写在前面

• Fibonacci numbers
• 斐波那契数列特点：
  • F₀ = 0,F₁ = 1;
  • F_n = F_n-1 + F_n-2;
  • such as:
    • 0, 1, 1, 2, 3, 5, 8, 13, 21 …

基础实现：递归实现

1
2
3
4
5
6
7

// 递归 Time: O(2^n) Space: O(1)
function fibonacci(n) {
  if (n <= 1) {
    return Math.max(n, 0);
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

初级实现：简单 for 循化实现

1
2
3
4
5
6
7
8
9
10
11

// 循环 Time: O(n) Space: O(n)
function fibonacci(n) {
  if (n <= 1) {
    return Math.max(n, 0);
  }
  let res = [0, 1]
  for (let i = 2; i < n; i ++) {
    res.push(res[i - 1] + res[i - 2])
  }
  return res[n - 1];
}

中级实现：简单 for 循化实现

// 递归优化，跳过计算过的中间变量 Time: O(n) Space: O(n)
// {
  let res = [0]
  function fibonacci(n) {
    if (n <= 1) {
      return res[n] = Math.max(n, 0);
    }
    if (res[n]) {
      return res[n];
    }
    res[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return res[n]
  }
  // 求数组第十项的值
  fibonacci(9)
// }

高级实现：矩阵乘法 + 快速幂

写在后面

• 祝大家多多发财