欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

五分钟重温斐波那契数列

程序员文章站 2024-03-19 20:52:52
...

斐波那契数列是数学领域内一个非常经典的算法问题(算法渣写下这句话的时候都在瑟瑟发抖),今天就用五分钟的篇幅来浅析一下这个问题。

什么是斐波那契数列?

1,1,2,3,5,8,13,21......
斐波那契数列从第三项开始,每一项都等于前两项之和。
斐波那契数列是由数学家 Leonardoda Fibonacci 以兔子繁殖为例子而提出的,所以也叫做“兔子数列”

当然了,为了和计算机领域结合起来,这个问题会变成:实现一个函数f(n),求斐波那契数列的第n项是多少?(n始终为正整数)

采用递归实现

有编程经验的你一定会想到递归。好的开始是成功的一半,如果你能想到递归,那么离成功已经不远了。
不难看出,数列的递推规律可以总结为:

f(n) = f(n-1) + f(n-2)

okay,挽起袖子开撸

五分钟重温斐波那契数列

乍一看,完美。
不过这个时候,但凡是个稍微有点追求的 Developer 都会说:“大兄弟你这么搞不是最优解呀,数字稍微大一点就炒鸡慢了。”

有缓存的 Fibonacci

虽然人艰不拆,但是优化还是要做的。
我不禁想到了前端性能优化里面最常见且好用的一条:缓存。大概的思路就是,将新算出来的值保存起来以便下一次使用。
Talk is cheap, show u the code

五分钟重温斐波那契数列

乍一看,又是完美。
还能优化吗?当然。
这里用数组作为缓存容器,当计算过 fibo(50) 时,数组的长度是51,在给最后一项赋值之前,js会将前50项都置为 undefined,自然会影响效率。
一行代码完成优化:

// let cache = [];
let cache = {};


生命不息,优化不止

优化是门学问,如果你还不肯善罢甘休的话,我也只能送你到这里了,毕竟本文的目的旨在帮你回忆起这么一道经典的题目(逃)。
如果某位数学大神看到了我这篇渣渣文,肯定会十分不屑的反手就是一个通项公式,emmmmm你开心就好。

最后

新年快乐 : )

五分钟重温斐波那契数列