斐波那契数列从O(2^n)到O(1)

0.斐波那契数列定义

常见的问题有爬楼梯问题：有n级楼梯，每次可以爬1级或者2级，问爬上n级有多少种爬法？这个问题与斐波那契数列只是初始条件不一样。

1.递归法

function fib1(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fib1(n - 1) + fib1(n - 2)
}
复制代码

递归法简单易懂，只是时间复杂太高。 比如求$fib(10)$。

$fib(10)=fib(9)+fib(8)$

$fib(9)=fib(8)+fib(7)$

$fib(8)=fib(7)+fib(6)$

从上面三个式子中发现$fib(8)、fib(7)$被计算了两次，当n较大时，会有更多的子项被多次计算，造成了计算冗余，时间复杂度高达O(2n)O(2^n)O(2n)。

2.备忘录递归法

既然发现$fib(8)、fib(7)$被重复计算了，那么我们用额外的空间将其结果进行存储，如果$fib(8)$没有被计算过，则进行计算，并将其存储，下次碰到$fib(8)$的时候直接从存储空间中获取，这样会节省很多时间。

function fib2(n) {
   let memory = new Array(n + 1).fill(0);
   const memo = (memory, k) => {
      if (k === 1 || k === 2) return 1;
      if (memory[k]) return memory[k];
      memory[k] = memo(memory, k - 1) + memo(memory, k - 2);
      return memory[k];
   };
   return memo(memory, n);
}
复制代码

时间复杂度$O(n)$，空间复杂度$O(n)$。

3.自底向上备忘录法

递归法在计算$fib(n)$时，都是从大的数进行计算，直到$fib(2)、fib(1)$，既然可以从大到小，那么也可以从小到大来填充备忘数组。

function fib3(n) {
   let memory = new Array(n + 1).fill(1);
   for (let i = 2; i < n; i++) {
      memory[i] = memory[i - 1] + memory[i - 2];
   }
   return memory[n - 1];
}
复制代码

这里$memory[0]=>fib2(1),memory[i]=>fib(i+1)$,所以$fib(n)=>memory[n-1]$。时间复杂度$O(n)$，空间复杂度$O(n)$。

4.丢掉备忘录吧

其实无需额外的空间，用变量记住前两个值，当前值等于前两个值相加，然后再更新前两个值，这样可将空间复杂度下降到$O(1)$。

function fib4(n) {
   if(n === 1 || n === 2) return 1;
   let pre = 1, cur = 1, sum = 2;
   for(let i = 3; i <= n; i++) {
       sum = pre + cur;
       pre = cur;
       cur = sum
   }
   return cur;
}
复制代码

5.通项公式法

梦回高中吧！（如果你正在读高中，当我没说）

已知:a1=1,a2=1,an+2=an+1+an(n>=1)已知:a_1=1, a_2=1,a_{n+2}=a_{n+1}+a_{n}(n>=1)已知:a1​=1,a2​=1,an+2​=an+1​+an​(n>=1)

构造:an+2−tan+1=k(an+1−tan)构造:a_{n+2} - ta_{n+1} = k(a_{n+1}-ta_n)构造:an+2​−tan+1​=k(an+1​−tan​)

=>an+2=(t+k)an+1−tkan=>a_{n+2}=(t+k)a_{n+1}-tka_n=>an+2​=(t+k)an+1​−tkan​

$对比已知得:t+k=1,tk=-1$

=>t(1−t)=−1=>t2−t−1=0=>t(1-t)=-1=>t^2-t-1=0=>t(1−t)=−1=>t2−t−1=0

=>t1=1+52,k1=1−52;t2=1−52,k2=1+52=>t_1=\frac{1+\sqrt{5}}{2},k_1=\frac{1-\sqrt{5}}{2};t_2=\frac{1-\sqrt{5}}{2},k_2=\frac{1+\sqrt{5}}{2}=>t1​=21+5​​,k1​=21−5​​;t2​=21−5​​,k2​=21+5​​

令bn=an+1−tan,则bn+1=an+2−tan+1,b1=a2−ta1=1−t=k令b_n=a_{n+1}-ta_n,则b_{n+1}=a_{n+2}-ta_{n+1},b_1=a_2-ta_1=1-t=k令bn​=an+1​−tan​,则bn+1​=an+2​−tan+1​,b1​=a2​−ta1​=1−t=k

于是bn+1=kbn=knb1=kn+1于是b_{n+1} = kb_n=k^nb_1=k^{n+1}于是bn+1​=kbn​=knb1​=kn+1

=>bn=kn=>an+1−tan=kn=>b_n=k^n=>a_{n+1}-ta_n=k^n=>bn​=kn=>an+1​−tan​=kn

$=>$

an+1−t1an=k1n⋯①a_{n+1}-t_1a_n=k_1^n\cdots①an+1​−t1​an​=k1n​⋯①

an+1−t2an=k2n⋯②a_{n+1}-t_2a_n=k_2^n\cdots②an+1​−t2​an​=k2n​⋯②

①−②=>(t2−t1)an=k1n−k2n①-②=>(t_2-t_1)a_n=k_1^n-k_2^n①−②=>(t2​−t1​)an​=k1n​−k2n​

an=k1n−k2nt2−t1=(1+5)n−(1−5)n2n5a_n=\frac{k_1^n-k_2^n}{t_2-t_1}=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}an​=t2​−t1​k1n​−k2n​​=2n5​(1+5​)n−(1−5​)n​

function fib5(n) {
   let sqrt5 = Math.sqrt(5);
   return (Math.pow(1 + sqrt5, n) - Math.pow(1 - sqrt5, n)) / (sqrt5 * Math.pow(2, n));
}
复制代码

由于精度问题可能会算出小数，这里暂不处理。

6.耗时测试

主要比较fib4与fib5的耗时，因为fib5虽然时间复杂度是$O(1)$,但是也是需要计算的。 测试代码：

const test = [
   1000000, 10000000, 100000000, 1000000000
];
for (let i = 0; i < test.length; i++) {
     let n = test[i];
     t1 = new Date().getTime();
     fib4(n);
     t2 = new Date().getTime();
     fib5(n);
     t3 = new Date().getTime();
     console.log("fib4", t2 - t1);
     console.log("fib5", t3 - t2);
}
复制代码

测试结果截图

由此可见，确实是$O(1)$的牛逼些！