从斐波那契数列说起

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

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

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

斐波那契数列

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

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

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

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

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

  • 通过循环的计算方式
    这种方法我是在看《剑指offer》上面看到的,我把它简化了一下,我觉得我简化后的代码很赞~凸^-^凸
    上代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /**
    * 通过循环实现
    *
    * 时间复杂度: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的资源,多线程必须要掌握啊~


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