当前位置: 首页 > >

Fibonacci数列的求解法

发布时间:

Fibonacci数列的求解法



题目:古典题目,有一对兔子,从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子都不死,问每个月的兔子总数为多少。对应的数列就是斐波那契(Fibonacci)数列。

3.表驱动的递归法:这里不提纯粹的表驱动法,因为对于项数未知的Fibonacci数列开启大片的空间来换取时间未免不值得且不负责。我们只是为了消除递归法中大量重复的运算,可以将已经计算过的中间值存入一个表,已备后续使用。当n小于保存的表长时,由于每个中间值只计算一次,时间复杂度降为O(n)。但随着n的增大,要想维持O(n)的时间复杂度,就必须扩大保存的表长,这就造成了存储空间的浪费。



时间复杂度:











posted on
2007-05-18 15:49?
岩山藤 阅读(
...) 评论(
...)
编辑
收藏



转载于:https://www.cnblogs.com/songshuqun/archive/2007/05/18/751593.html






相关资源:Fibonacci数列的四种解:递归、存储优化的递归、自下而上的递归(迭代)、尾递归



友情链接: