网站首页 > 心得体会> 文章内容

C语言经典的算法斐波那契数列的几种求法递归一定好吗

※发布时间:2018-5-16 7:31:47   ※发布作者:habao   ※出自何处: 

  由于代码直接复制来显示不太美观,故我就直接放截图啦,同时也是为了避免大家直接复制代码运行,对于初学者,我还是毕竟大家自己敲一遍代码的,这样印象会更加深刻。

  以上这种方法是最常见也是我们容易理解的方法,直接利用了斐波那契数列的数学公式:f(n)=f(n-1)+f(n-2)。

  到这里,初学者应该已经懵了,代码编写好,能输出结果就可以了嘛,“时间复杂度”是什么鬼?为什么我们还要讨论“时间复杂度”这个东西呢?

  这就是算法里需要讨论的问题了,很多时候【初学C语言】,我们的程序只要求准确性就好了,只要能输出正确结果,我们就满足了,但是,在更多时候,我们要求我们的代码不仅能正确输出结果,还要在的时间内输出结果,这个时候,时间复杂度太大的程序就不可行了。

  你想想,如果我编写了一个程序,输出一个结果要用整整一天甚至一个月,一年,想起来是不是不可接受?所以,我们要对时间复杂度特别大的代码进行优化,让代码在我们能接受的时间范围内输出正确的结果。

  反正,你只要记住,的递归方法求斐波那契数列是一个时间复杂度为指数级别的程序,这个复杂度是一个相对来说很大的复杂度,当n很大的时候,其实不用很大,n=1000甚至n=100,50的时候,就能很明显地感受到这个方法输出结果特别慢。因为它要重复计算很多已经计算过的式子。

  这个方法也很好理解,循环把前两个数加起来赋值给第三个,这种方法只for循环一次,故时间复杂度为O(n),比起前面的递归来说实在好太多了。

  所以你看呐,初学者一般会以为递归的方法比求解的方法更好,事实上并不完全如此,所有的方法都有它的好处和缺点,尤其是在计算机领域,到目前还没有找到一种方法任何一个地方都好。

  

关键词:c语言体会