admin 管理员组

文章数量: 1086019


2024年3月13日发(作者：oracle完整版)

斐波那契数列 算法

斐波那契数列是一种非常经典的数列，其定义是：第一项和第二

项均为1，从第三项开始，每一项都是前两项的和。即：1, 1, 2, 3,

5, 8, 13, 21, 34, 55……

计算斐波那契数列的方法有很多，以下是两种常见的方法。

方法一：递归算法

递归算法是一种自己调用自己的算法。对于斐波那契数列，递归

算法可以这样实现：

```python

def fib(n):

if n == 1 or n == 2:

return 1

else:

return fib(n-1) + fib(n-2)

```

该算法的时间复杂度为O(2^n)，因为每个数都需要递归计算其

前两个数，所以计算量会指数级增长。因此，该算法只适用于计算比

较小的数列。

方法二：迭代算法

迭代算法是一种循环计算的算法。对于斐波那契数列，迭代算法

可以这样实现：

```python

- 1 -

def fib(n):

if n == 1 or n == 2:

return 1

else:

pre1, pre2 = 1, 1

for i in range(3, n+1):

cur = pre1 + pre2

pre1, pre2 = pre2, cur

return cur

```

该算法的时间复杂度为O(n)，因为只需要循环计算n-2次，所

以计算量是线性增长的。因此，该算法适用于计算任意长度的数列。

总结

两种算法各有优缺点，递归算法代码简单易懂，但效率低；迭代

算法效率高，但代码稍微复杂一些。在实际应用中，应根据需要选择

合适的算法。

- 2 -


本文标签： 算法 计算 迭代 循环 适用

版权声明：本文标题：斐波那契数列 算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710259206a564847.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。