为什么这样写显著提升了Fibonacci sequence性能??-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

为什么这样写显著提升了Fibonacci sequence性能??

蛮大人123 2016-02-25 13:58:20 1575

题目如下:
在计算机上运行一下程序:
screenshot
计算机用这段程序在一小时内能得到的F(N)结果的最大N值是多少?开发F(N)的一个更好的实现,用数组保存已经计算的值。
首先我在计算机上运行上面程序,如下:
screenshot
发现用上面题目给出的方法运行到N = 40多时,程序已经明显慢下来了,
问题1:慢下来是因为处理的数据太大了,而且每次都要再次计算?还是因为其他什么原因?
问题2:题目中要预测计算机在一小时内能够得到F(N)结果的最大N值,这个怎么做?
题的代码,如下:
screenshot
screenshot
再次运行时,居然在1秒多就运行完了:
问题3:
很好奇为什么这么快,自己尝试分析下,用N=0,1,2,3试,但是在Fib函数中为什么要if (f[N] == 0)呢?数组最后一个元素为0?
是因为用数组 f 保存已经计算过的值了,所以不需要再重新计算了所以才快了很多吗?
问题4:
最后结果从93行开始,93,95,96,97,99行出现的负数,大致知道是和操作系统运算有关,但又不是很清楚,求解释?

分享到
取消 提交回答
全部回答(1)
  • 蛮大人123
    2019-07-17 18:47:26

    问题1就是保存了中间结果
    问题2我也不肯定,我猜这个运算时间也是斐波那契数列
    问题3的f(N)==0是用来判断这个值有没有计算过的,计算过直接调用已保存的结果,没计算过的f(N)是0,就进行if立面的计算
    问题4是long长度越界了。

    0 0
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

推荐文章