<small id='gR6Nensy7'></small> <noframes id='5aN8m4rS'>

  • <tfoot id='mnrHAZs2eJ'></tfoot>

      <legend id='1gE76bh5Z'><style id='CER3lyikY'><dir id='G4T9ynKNjE'><q id='xWt9fbC54Y'></q></dir></style></legend>
      <i id='celY8'><tr id='duD2'><dt id='2B4C'><q id='KnDsTR1uW'><span id='P5cz'><b id='rjzyfkgF'><form id='ZbjvgE'><ins id='sJpteWciaj'></ins><ul id='JDoCb'></ul><sub id='7bOu'></sub></form><legend id='np2CD4hg'></legend><bdo id='n0QEuZ'><pre id='bzd2'><center id='FRzu'></center></pre></bdo></b><th id='BnryecQ'></th></span></q></dt></tr></i><div id='xY84'><tfoot id='ec4G'></tfoot><dl id='haYdvK3g'><fieldset id='51J3PtX7'></fieldset></dl></div>

          <bdo id='u1dIGw8ksE'></bdo><ul id='inEyVGhYAo'></ul>

          1. <li id='6ENPq7jgJ'></li>
            登陆

            除了递归你还会用其他办法完成斐波那契数列么?

            admin 2020-02-14 264人围观 ,发现0个评论

            斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368......

            我记住在初学C言语的时分,大学教师常常会讲一些常见的数学问题及递归的运用,其间斐波那契数列便是必定会被拿出来举例的。在后来工作中,面试做面试题的时分,也很大概率会呈现编写算法完成斐波那契额数列求值。能够说,在咱们编程道路上,编写算法完成斐波那契数列是每个程序员必定会做的一件事。昨日去参与腾讯讲堂举行的一个线下活动,活动中有一位嘉宾,是某讲堂的创始人,也是算法课程的讲师,就讲到了这个问题,算是推翻了我对该问题的认知。本文就依据这名讲师的解说,来剖析和收拾一下该问题算法的完成。

            下面,咱们来看看其间几种常见的算法,并剖析其功率。

            1、递归法

            经过调查,咱们会发现其间的规则,第一项和第二项的值均为1,后边每项的值都是前两项值之和,所以咱们许多人基本上都会运用递归来完成,常见的算法如下:

            1 public int fib(int n) {
            2 if (n == 1 || n == 2) {
            3 return 1;
            4 }
            5 return fib(n - 2) + fib(n - 1);
            6 }

            这段代码看起来十分的简练和高雅,我想咱们绝大多数的人平常也都是这么写的吧,在此之前笔者就一向都是这么写的,并且在我的常识储藏中也就只知道有这样一种算法。

            实践上,当n还比较小的时分,用递归法来完成是没有什么问题的,可是当n略微大一点的时分,比方n=45的时分,咱们经过如下测验代码来看看它的履行成果:

            1 MyClass myClass = new MyClass();
            2 long t1 = System.currentTimeMillis();
            3 int n = 45;
            4 int result = myClass.fib(n);
            5 long t2 = System.currentTimeMillis();
            6 System.out.println("n=" + n + ";result=" + result + ";time=" + (t2 - t1));

            得到成果为:

            n=45除了递归你还会用其他办法完成斐波那契数列么?;result=1134903170;time=2881

            咱们发现履行这段代码,花费的时刻是2881ms。假如值再大一点,如n=48:

            n=48;result=512559680;time=11746

            时刻达到了11s以上了!假如n再略微大一点,所耗费的时刻是成指数级增加的,比方n=64的时分,所耗费的时刻可能是两三百年!不信的话,读者能够试试!

            这样看来,就十分可怕了,咱们一向以为毫无问题的看起来既简练又高雅的算法,居然是这么耗时的,这简直便是一段废物代码。

            咱们用一张图来简略剖析一下该算法的履行进程,以n=6为例:



            咱们会发现f(n)这个办法被调用了很屡次,并且其间重复率十分之高,也便是说被重复核算了很屡次,假如n略微大一点这棵树会十分巨大。这儿咱们能够看出,每个节点就需求核算一次,总核算的次数便是该二叉树节点的数量,可见其时刻复杂度为O(2n),是指数级的,其空间复杂度也便是该二叉树的高度,为O(n)。这样来看,咱们应该就清楚了,为什么这段代码功率如此低下了吧。

            2、数组保存法(该名称是自己命名的,想不出什么好姓名了,不喜勿喷哈...)

            为了防止无数次重复,能够从n=1开端往上核算,并除了递归你还会用其他办法完成斐波那契数列么?把每一个核算出来的数据,用一个数组保存,需求最终值时直接从数组中取即可,算法如下:

            1 public int fib(int n) {
            2 int[] fib = new int[n];
            3 fib[0] = 1;
            4 fib[1] = 1;
            5 for (int i = 2; i < n; i++) {
            6 fib[i] = fib[i - 2] + fib[i - 1];
            7 }
            8 return fib[n - 1];
            9 }

            咱们也别离取n=45和n=48来看看履行成果

            n=45;result=1134903170;time=0
            n=48;result=512559680;time=0

            耗费的时刻都是0(我这儿获取的时刻是准确到ms等级的,前后的时刻差在1ms以下,所以这儿核算出来的成果为0,实践耗时不行能为0,后续不赘述),可见履行功率提高了许多。这种算法主要有一个for循环,其时刻复杂度为O(n),期间需求拓荒一个长度为n的数组,所以空间复杂度也为O(n),这就在上述算法的基础上极大地提升了功率。

            3、翻滚数组法(这个命名是读者谈论区提出来的,尽管不是很了解,不过仍是采用吧,总比我自己瞎命名好,感谢这位童鞋)

            尽管上述算法现已很高效了,但咱们仍是会发现一个问题,其实整个数组中,每次核算时都只需除了递归你还会用其他办法完成斐波那契数列么?求最新的3个值,前面的值核算完后就不再需求了。比方,核算到第10次时,需求的数组空间只要第8和第9两个空间,前面第1到第7个空间其实就不再需求了。所以咱们还能够改善,经过3个变量来存储数据,算法如下:

             1 public int fib(int n) {
            2 i除了递归你还会用其他办法完成斐波那契数列么?nt first = 1;
            3 int second = 1;
            4 int third = 2;
            5 for (int i = 3; i <= n; i++) {
            6 third = first + second;
            7 first = second;
            8 second = third;
            9 }
            10 return third;
            11 }

            时刻复杂度依然为O(n),而空间复杂度为常量等级3,即空间复杂度为0,所以这种办法是十分高效的。

            4、公式法

            实践上,求斐波那契数列值有一个公式:



            能够经过该公式来完成算法:

            1 public int fib(int n) {
            2 double c = Math.sqrt(5);
            3 return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
            4 }

            其时刻复杂度和空间复杂度就取决于JDK中这些数学公式的完成了,履行功率也是十分高的:

            n=48;result=512559680;time=0

            5、尾递归法

            这儿先亮出该算法吧:

            1 public int fib5(int n, int first, int second) {
            2 if (n <= 1) {
            3 return first;
            4 } else {
            5 return fib5(n-1,second,first+second);
            6 }
            7 }

            其实我起先觉得这种办法的完成和第三种算法的中心思想挺相似的,尽管乍一看如同不同挺大,但细心剖析,也都是经过两个变量保存核算值,传递给下一次大航海时代ol进行核算,递归的进程中也是依据n值改变逐渐重复运算,和循环差不多,时刻复杂度和空间复杂度也都相同,所以开始就没有独自列出来。后来谈论区有童鞋提出来了,细心想想,这种办法从形式上和第三种算法不同仍是挺除了递归你还会用其他办法完成斐波那契数列么?大的,并且简练许多,高除了递归你还会用其他办法完成斐波那契数列么?雅许多,也有一个嘹亮的姓名,仍是独自列出来更好,这儿也感谢谈论区童鞋们的宝贵意见。

            6、矩阵快速幂法

            本办法是在谈论中才知道的,我也在其网上搜了一下该办法,惋惜当年学的矩阵常识都又还给教师了,一时半会我是真看不懂,这儿我也就不打肿脸充胖子了,给个链接:https://blog.csdn.net/computer_user/article/details/86927209,有剖析进程和完好的java完成代码。

            作者:宋者为王

            原文:斐波那契数列

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP