首页 / 更多教程 / 剑指offer-斐波那契数列
剑指offer-斐波那契数列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer-斐波那契数列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1208字,纯文字阅读大概需要2分钟。
内容图文
![剑指offer-斐波那契数列](/upload/InfoBanner/zyjiaocheng/1038/fe24f50b98c3442d98910ce523bd5a7b.jpg)
首先,说一下斐波那契数列的定义:
又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、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*),也就是下一个数值是它前紧邻两个数值的和。
直接上代码:
//方法一:最简单直接的方法,但是时间复杂度O(2^n),空间复杂度o(1) public class Solution{ public int Fibonacci(int n){ if(n<=1){ return n; } return Fibonacci(n-1)+Fibonacci(n-2); } } //方法二:优化递归,时间复杂度O(n),空间复杂度O(n) public class Solution { public int Fibonacci(int n) { int a[] = new int[40]; a[0] = 0; a[1] = 1; for(int i =2;i <= n; i++){ a[i] = a[i-1]+a[i-2]; } return a[n]; } } //方法三:优化存储,时间复杂度O(n),空间复杂度O(1) public class Solution { public int Fibonacci(int n) { if(n<2){ return n; } //时间复杂度:O(n) //空间复杂度:O(1) int sum =0; int two = 0; int one = 1; for(int i=2;i<=n;i++){ sum = two + one; two = one; one = sum; } return sum; } } //方法四:在方法三的基础上持续优化 public class Solution{ public int Fibonacci(int n){ if(n<2){ return n; } int sum =1; int one =0; for(int i=2;i<=n;i++){ sum =sum +one; one = sum -one; } return sum; } }
内容总结
以上是互联网集市为您收集整理的剑指offer-斐波那契数列全部内容,希望文章能够帮你解决剑指offer-斐波那契数列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。