实现斐波那契数列（js），以及复杂度降阶

实现斐波那契数列（js），以及复杂度降阶

背景——兔子数列

假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每个月会生1对兔子，兔子永远不会死去……那么，由1对兔子开始，12个月后会有多少对兔子呢？

问题分析：

我们拿新出生的1对小兔子分析，

第1个月，小兔子a没有繁殖能力，所以还是1对。

第2个月，小兔子a进入成熟期，仍然是1对。

第3个月，兔子a生了1对小兔子b，于是这个月共有2（1+1）对兔子。

第4个月，兔子a又生了1对小兔子c，因此共有3（1+2）对兔子。

第5个月，兔子a又生了1对兔子d，而在第3个月出生的兔子b也生下了1对小兔子e，于是共有5（2+3）对兔子

……

从分析中可以看出，这个数列有一个很明显的特点，即从第3个月开始，当月的兔子数＝上月兔子数+当月新生兔子数，而当月新生的兔子数正好是上上个月的兔子数。因此：当月的兔子数=上月兔子数+上上月兔子数。这就是著名的斐波那契数列，又称为黄金分割数列。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 35 …

表达式为：

斐波那契数列表达式

算法设计

1. 递归——简单粗暴 代码： /* 递归 */ function fb1(n) { if (n < 1) return -1; if (n == 1 || n == 2) return 1; return fb1(n - 1) + fb1(n - 2); } console.log(fb1(12));//144 时间复杂度：O(2^N) 空间复杂度：O(N) 时间复杂度是指数阶，属于爆炸增量函数，在程序设计中我们应该避免这样的复杂度。
2. 改进——空间换时间 第一种解法比较简单，但是多个元素重复计算，因而时间复杂度较高，为了避免重复计算，可进行数组保存一下每一次计算的结果，减少时间复杂度。 代码： /* 数组 */ function fb2(n) { if (n < 1) return -1; if (n == 1 || n == 2) return 1; var res = [1, 1]; for (var i = 2; i < n; i++) { res[i] = res[i - 1] + res[i - 2]; } return res[n - 1]; } console.log(fb2(12));//144 时间复杂度：O(2^N) 空间复杂度：O(N)
3. 改进——降空间复杂度 观察第二种解法，其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次计算使用，根部不需要记录。因此可以再次优化。 代码： /* 迭代 */ function fb3(n) { let num1 = 1, num2 = 2, num3 = 0; if (n < 1) return -1; if (n == 1 || n == 2) return 1; for (let i = 3; i < n; i++) { num3 = num1 + num2; num1 = num2; num2 = num3 } return num3 } console.log(fb3(12));//144 时间复杂度：O(N) 空间复杂度：O(1)

生活中的斐波那契数列

科学研究发现植物的叶、枝、茎的排列很多符合斐波那契数列！向日葵的种子圈数和种子数，菠萝外表排序等。植物的枝丫也满足斐波那契数列，这就是生物学中的“鲁德维个定律”。

植物并不懂得斐波那契数列，这是自然选择的结果，这些植物的排列方式可以使得植物种子大小相近而且疏密得当。这就需要我们自然界最美好的数，黄金分割数：0.618！

再看我们的斐波那契数列，它是一个自然数的数列，然而通项公式却是用无理数来表达的。而且当n趋向于无穷大时，斐波那契数列前一项和后一项的比值越来越接近黄金分割比0.618！

两项之比接近黄金分割比

参考书籍：《趣学算法》——陈小玉著