啥是斐波那契数列？

相信大家都不陌生,在高中数学中都有接触过,斐波那契数列以如下被以递推的方法定义：

F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

程序中的斐波那契数思想

我们平时用编程语言编写的递归方法，其实就是斐波那契数列表达式，而表达式是可以推导出通项公式的，这也是斐波那契数列在程序中最好的思想表达。

分析斐波那契数列的实现过程

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

代码实现

方案一

最精简通过递归，但是时间复杂度很高 O(n^2)，执行分析结果如下:

/** * @param {number} N * @return {number} */var fib = function(N) {    if (N<=1) return N;    return fib(N-1) + fib(N-2);};

方案二

for 循环，用两个变量保存前两项斐波那契数即可。并且变量交换时也无需临时变量，空间复杂度 O(N)

/** * @param {number} N * @return {number} */var fib = function(N) {    if (N<2) return N;    var frist = 0;    var second = 1;    for (var i=2;i<=N;i++) {        second = frist + second;        frist = second - frist;    }    return second;};

方案三

这个空间复杂度与时间复杂度都仅需 O(N)，while 循环实现

/** * @param {number} N * @return {number} */var fib = function(N) {   var f = first,second =1;    if (N == 0)  return 0;        while(--N) {            second = second + first;            first= second-first;        }        return second;};

方案四

斐波那契通项公式

/** * @param {number} N * @return {number} */var fib = function(N) {  return Math.floor((Math.sqrt(5) / 5) * ( Math.pow((1 + Math.sqrt(5)) / 2, N) -  Math.pow((1 - Math.sqrt(5)) / 2, N)))}