斐波那契数列(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)

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