文档章节

从斐波那契数列说起

那只是一股逆流
 那只是一股逆流
发布于 2017/03/26 17:32
字数 1059
阅读 22
收藏 0

这段时间在看算法相关的一些东西;

因为算法不好连笔试都过不了(哭,其实算法不仅仅是为了笔试面试,更是为了日后在工作中提高软件的运行效率。这让我联想到了前不久看过的一篇文章: 李开复:算法的力量

以前没有重视算法,现在都要该还回来啦;

斐波那契数列

今天看到斐波那契数列感觉很有意思; 斐波那契数列:

f(0) = 0;
f(1) = 1;
f(n) = f(n-1) + f(n-2) n>2;

嗯,不是很复杂,实现起来也很简单,但是不同的斐波那契数列的实现,执行时间存在巨大差异!!! 我写了三种实现方式,地址在这 -》 斐波那契数列三种实现

  • 存在重复计算的递归方式 我们很容易通过递归的方式计算斐波那契数列,这也是最简洁的一种方式,代码量非常少。 但是这种方式存在大量重复计算的项,如:
f(9) = f(8)+f(7);
f(8)=f(7)+f(6);
f(7)被重复计算了,当所求的项比较多的时候重复计算的项就比较多了

  • 无重复计算的递归方式 重复计算很严重的影响效率,那么我们保存上一项计算的结果值留给下一次计算使用就行了。 相对于上面那种方式,这种方式更像是从上往下计算,从0开始计算直到n
f(8)=f(7)+f(6); //保留f(7)和f(8)的值留给下一次运算使用
f(9)=f(8)+f(7); //f(7)和f(8)的值直接从上一次运算获取


  • 通过循环的计算方式 这种方法我是在看《剑指offer》上面看到的,我把它简化了一下,我觉得我简化后的代码很赞~凸^-^凸 上代码:

/**
 * 通过循环实现
 *
 * 时间复杂度:o(n)
 * 空间复杂度:o(1)
 *
 * @param n
 * @return
 */
public long fByLoop(int n) {
    
    long[] result = {0, 1};
    for (int i = 2; i < n + 1; i++) {
        result[i & 1] += result[(i + 1) & 1];
    }
    return result[n & 1];
}


从斐波那契数列说起:谈谈我的感想

我把三种实现写出来以后,我想跑一下看谁比较快,书上说那种带有重复计算的递归方式很慢,于是我就顺便测一下。 测试结果令我大跌眼镜, 计算一百项斐波那契数列

使用重复计算的递归方式计算一百项的斐波那契数列时,计算了四十分钟还没有计算出来,我一度怀疑我的代码有没有问题。无奈,只好把项数减少到五十,才顺利的拿到结果: 计算五十项斐波那契数列

我们可以看到,存在重复计算的递归方式耗时是其他方式的20万倍左右,好恐怖!

要是再生产环境中存在这样的算法,再多的服务器都坑不住。看来自己还是要多多练习算法,多多思考,精益求精,才能感受到编程之美;否则一股脑写的代码是堆上去的,自己也就得不到任何的提升。

再来感受一下算法的力量: 李开复:算法的力量

其它

计算一百项的时候,我打开了visualvm查看了一下jvm的运行状况,发现了一个有趣数据: 统计信息 我们看CPU的数据,发现使用率一直停留在25%左右。 因为我的电脑是双核四线程,而我们的程序是单线程的,最多只能使用25%的CPU资源。 哈哈,看来要榨干CPU的资源,多线程必须要掌握啊~


计算一百项的斐波那契数列,现在还没计算出来(。ì _ í。)

© 著作权归作者所有

共有 人打赏支持
那只是一股逆流
粉丝 9
博文 22
码字总数 26214
作品 0
南岸
后端工程师
私信 提问
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
08/11
0
0
python有趣的小编程

斐波那契数列的计算 描述 斐波那契数列(Fibonacci sequence),又称黄金分割数列,由意大利数学家Leonardo Fibonacci于1202年提出,并以其名字命名。该数列F(n)定义如下:F(0)=0, F(1)=1,...

巍峨大山
2017/01/04
791
5
使用递归解决斐波那契数列的性能问题

我们知道斐波那契数列(也称作兔子数列) 1,1,2,3,5,8,13,21,34。。。。。 前两位数固定是1,之后每一位数都是前两位数的之和,这样的数列就是斐波那契数列 那么我们要求这样的数列,就必须要...

爱碎了夏天
08/07
0
0
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity
2014/06/20
0
0
python实现斐波那契数列

斐波那契数列的发明者是意大利数学家昂纳多.斐波那契(Leonardo Fibonacci)。斐波那契数列又被称为黄金分割数列,或兔子数列。它指的是这样一个数列:0 1 1 2 3 5 8 13 21 34 ....在数学上,...

大陌
2017/07/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring源码学习笔记-1-Resource

打算补下基础,学习下Spring源码,参考书籍是《Spring源码深度解析》,使用版本是Spring 3.2.x,本来想试图用脑图记录的,发现代码部分不好贴,还是作罢,这里只大略记录下想法,不写太细了 ...

zypy333
今天
10
0
RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
今天
17
0

中国龙-扬科
昨天
2
0
Linux系统设置全局的默认网络代理

更改全局配置文件/etc/profile all_proxy="all_proxy=socks://rahowviahva.ml:80/"ftp_proxy="ftp_proxy=http://rahowviahva.ml:80/"http_proxy="http_proxy=http://rahowviahva.ml:80/"......

临江仙卜算子
昨天
11
0
java框架学习日志-6(bean作用域和自动装配)

本章补充bean的作用域和自动装配 bean作用域 之前提到可以用scope来设置单例模式 <bean id="type" class="cn.dota2.tpye.Type" scope="singleton"></bean> 除此之外还有几种用法 singleton:......

白话
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部