1.斐波那契数列
规律：f(1) =1 f(2)=1 … f(n)=f(n-1)+f(n-2)
2.代码部分
2.1 递归写法
- 时间复杂度指数级别 2^n
- 空间复杂度 o(N）
public static int fib(int n){
if(n<1){
return -1;
}
if(n==1 || n==2){
return 1;
}
return fib(n-1)+fib(n-2);
}
2.2 利用数组优化时间复杂度
- 时间复杂度指数级别 o(N)
- 空间复杂度 o(N）
public static int fib2(int n){
if(n<1){
return -1;
}
if(n==1 || n==2){
return 1;
}
int[] f =new int[n+1];
f[1]=1;
f[2]=1;
for(int i=3;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
2.3 利用数值替换优化空间复杂度
- 时间复杂度指数级别 o(N)
- 空间复杂度 o(1）
public static int fib3(int n){
if(n<1){
return -1;
}
if(n==1 ||n==2){
return 1;
}
int fn=0;
int f1=1;
int f2=1;
for(int i=3;i<=n;i++){
fn=f1+f2;
f1=f2;
f2=fn;
}
return fn;
}
