沒有緩存的Fibonacci會做大量重復的計算。
public static int fibonacci(int num){
if (num ==1 || num ==2){
return 1;
? ? }else{
return fibonacci(num-1) +fibonacci(num-2);
? ? }
}
當賦值為 60 時，已無法在數(shù)十秒鐘的時間內(nèi)算出來了。JDK 1.8，i5，內(nèi)存 16G。
---------------------分割線---------------
可以用數(shù)組記錄下已經(jīng)算過的數(shù)據(jù)。改進后的算法如下。
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做測試，結(jié)果秒出。
