斐波那契数列_07
2023-04-18 16:10:08 时间
1.普通递归
public int fibonacci(int n) {
if (n==1||n==0){
return n;
}else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
时间复杂度:o(2n) 空间复杂度:o(1)
1.这种递归会产生许多相同的计算,我们可以不用递归,顺序计算即可
public int Fibonacci(int n) {
int [] nums=new int[40];
nums[0]=0;
nums[1]=1;
for (int i = 2; i <= n; i++) {
nums[i]=nums[i-1]+nums[i-2];
}
return nums[n];
}
时间复杂度:o(n) 空间复杂度:o(n)
优化存储
分析 其实我们可以发现每次就用到了最近的两个数,所以我们可以只存储最近的两个数
sum 存储第 n 项的值 one 存储第 n-1 项的值 two 存储第 n-2 项的值
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n == 1){
return 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;
}
}
时间复杂度:o(n) 空间复杂度:o(1)
再次优化
sum 只在每次计算第 n 项的时候用一下,其实sum,tow,one本身就有一个算数和的运算关系,所以其实还可以利用 sum 存储第 n-1 项,例如当计算完 f(5) 时 sum 存储的是 f(5) 的值,当需要计算 f(6) 时,f(6) = f(5) + f(4),sum 存储的 f(5),f(4) 存储在 one 中,由 f(5)-f(3) 得到
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}
//用于存放n-1时候的值
int sum=1;
int one=0;
for (int i = 2; i <= n; i++) {
sum=sum+one;
one=sum-one;
}
return sum;
}
相关文章
- 直接在代码里面对list集合进行分页
- .NET Framework 4.5新特性详解
- 大数据的简要介绍
- 大数据的由来
- 高斯混合模型的自然梯度变量推理
- timing-wheel 仿Kafka实现的时间轮算法
- 使用Navicat软件连接自建数据库(Linux系统)
- 那一天,我被Redis主从架构支配的恐惧
- Redis 深入了解键的过期时间
- C#使用委托调用实现用户端等待闪屏
- 基于流计算 Oceanus 和 Elasticsearch Service 构建百亿级实时监控系统
- GRAND | 转录调控网络预测数据库
- JFreeChart API中文文档
- 临床相关突变查询数据库
- TIGER | 人类胰岛基因变化查询数据库
- 视频边缘计算网关EasyNVR在视频整体监控解决方案中的应用分析
- Apache Arrow - 大数据在数据湖后的下一个风向标
- 常见的电商数据指标体系
- AKShare-艺人数据-艺人流量价值
- MySQL中多表联合查询与子查询的这些区别,你可能不知道!