没有缓存的Fibonacci会做大量重复的计算。
public static int fibonacci(int num){
if (num ==1 || num ==2){
return 1;
}else{
return fibonacci(num-1) +fibonacci(num-2);
}
}
当赋值为 60 时，已无法在数十秒钟的时间内算出来了。JDK 1.8，i5，内存 16G。
---------------------分割线---------------
可以用数组记录下已经算过的数据。改进后的算法如下。
private static BigInteger[]fib_cache =new BigInteger[100000];
public static void main(String[] args){
System.out.println(fibonacci_arr(10000));
for (int i =0;i
if (fib_cache[i] !=null) {
System.out.print(fib_cache[i] +" ");
}
}
}
public static BigIntegerfibonacci_arr(int num){
if (fib_cache[num-1] !=null){
return fib_cache[num-1];
}
BigInteger value;
if (num ==1 || num ==2){
value =new BigInteger("1");
}else {
value =fibonacci_arr(num -1).add(fibonacci_arr(num -2));
}
fib_cache[num-1] = value;
return value;
}
用10000做测试，结果秒出。
