2025年斐波那契数列的5种算法

斐波那契数列的5种算法斐波那契数列 Fibonacci sequence 又称黄金分割数列 因数学家莱昂纳多 斐波那契 Leonardo Fibonacci 以兔子繁殖为例子而引入 故又称为 兔子数列 指的是这样一个数列 1 1 2 3 5 8 13 21 34 在数学上

大家好,我是讯享网,很高兴认识大家。

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)

一、循环法:

 

// n 太大会溢出,可以使用数据位更宽的数据类型 int fib(int n){ if(n==1||n==2) return 1; int f1=1; int f2=1; int res=0; //存放结果 for(int i=3;i<=n;++i){ res=f1+f2; f2=f1; f1=res; } return cur; }

讯享网

时间复杂度:O(n)

空间复杂度:O(1)


讯享网

二、递归法:

根据递推公式:F(n)=F(n - 1)+F(n - 2)可直接得出

讯享网int fib(int n){ if(n<2) return n; return fib(n-1)+fib(n-2); }

时间复杂度:因为成二叉树形式 ,所以时间复杂度为O(2^n)

空间复杂度:树约有n-1层,所以空间复杂度为O(n)

三、动态规划法:

1. 确定 dp数组以及下标的含义:dp[i] 的定义为:第 i 个数的斐波那契数值是 dp[i]
小讯
上一篇 2025-01-19 19:26
下一篇 2025-02-21 19:14

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76922.html