两个斐波拉切数列运算的时间复杂度

2018-02-27 11:50:19来源:oschina作者:算法之名人点击

分享

有人提出了递归算法的时间复杂度问题,的确如此,递归的时间复杂度是随着数量级成指数增长的。


现在补充一个时间复杂度线性增长的方法。多谢朋友的指正。


import java.util.Scanner;
/**
* Created by Administrator on 2018-02-15.
*/
public class Fibonacci {
public static long FibonacciQty(int n) {
long t1,t2;
if(n == 1 || n == 2) {
return 1;
}else {
t1 = FibonacciQty(n-1);
t2 = FibonacciQty(n-2);
return t1+t2;
}
}
public static long FibonacciQty2(int n) {
long t1 = 1;
long t2 = 1;
if(n == 1 || n == 2) {
return 1;
}else {
for (int i = 2;i < n - 1;i++) {
t2 = t1 + t2;
t1 = t2 - t1;
}
return t1+t2;
}
}
public static void main(String[] args) {
System.out.println("递推算法求解兔子产仔问题!");
System.out.print("请先输入时间:");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
long num = Fibonacci.FibonacciQty2(n);
System.out.println("经过"+n+"月的时间,共能繁殖成"+num+"对兔子!");
}
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台