2 tuyf hs tuyf_hs 于 2015.06.22 22:07 提问

斐波那契数列的性能优化 10C

http://www.nowcoder.com/books/coding-interviews/c6c7742f5ba7442aada113136ddea0c3?rp=1

牛客网上 的这道题,一个简单的递归,性能不满足要求,请问 有什么提高性能的算法

5个回答

lrgdongnan
lrgdongnan   2015.06.23 00:16

递归性能当然差了,解决档案是:将递归改为迭代!

zhjchengfeng5
zhjchengfeng5   2015.06.23 12:25

为啥不直接上通项公式

lrgdongnan
lrgdongnan   2015.06.23 12:36

图片说明

这是我写的源代码。接下来我将对递归和迭代进行分析,我觉得这才是重点!

lrgdongnan
lrgdongnan   2015.06.23 13:00

在大部分情况下,递归和迭代可以相互转化。递归的好处是程序简单明了,易于理解;缺点是效率低,为什么呢?因为递归过程中存在着大量的重复计算,举例说明:在计算F(5)时,程序要递归计算F(3)和F(4),而在计算F(4)时,又要递归计算F(2)和F(3),有没有发现在计算F(4)时又重复计算了一次
F(3)。这种情况在递归过程中是很多的,为了便于理解,给出计算F(4)的递归调用流程图,你可以发现n取值越大,重复计算的越多:
图片说明

lrgdongnan
lrgdongnan   2015.06.23 13:06

而对于迭代,不存在重复计算的问题,迭代的思想是:为了计算第n项,依次将前面n项(从第0项开始)求出并保存起来,计算每一项是直接调用保存的值,即它前面的两项值。

Csdn user default icon
上传中...
上传图片
插入图片