斐波那契数列优化

斐波那契数列是什么

斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2) 其中 n是大于等于2的整数。

简单实现

首先想到的就是递归

function fib(n) {
  if(n === 0) return 0
  if(n === 1) return 1
  return fib(n-1) + fib(n-2)
}
console.log(fib(100))

代码很简洁，但性能不佳。比如计算 fib(7)

fib(7) = fib(6)+fi(5)
       = fib(5)+fib(4) + fib(4)+fib(3)
       = fib(4)+fib(3)+fib(3)+fib(2) + fib(3)+fib(2)+fib(2)+fib(1)
       = fib(3)+fib(2)+fib(2)+fib(1)+fib(2)+fib(1)+fib(1)+fib(0)+......

时间复杂度为O(2^n)

空间换时间

function fib(n) {
  let dict = [0n, 1n]
  for(let i=2; i<=n; i++) {
    dict[i] = dict[i-1] + dict[i-2]
  }
  return dict[n]
}
console.log(fib(1000))

时间复杂度为O(n)，空间复杂度为O(n)

优化空间

function fib(n) {
  let [v1, v2] = [0n, 1n]  //这里用bigInt类型
  for(let i=2; i<=n; i++) {
    [v1, v2] = [v2, v1+v2]
  }
  return v2
}
console.log(fib(1000))

时间复杂度为O(n)，空间复杂度为O(1)。完美。