java優化遞歸求斐波那契數列

優化遞歸求斐波那契數列

斐波那契數列在我們遞歸學習中是一個基本的算法。今天我們也學習了遞歸，也做了關于求斐波那契第n項的算法，發現普通的遞歸斐波那契的計算效率很局限，在第50項左右都很吃力了，對此我又對斐波那契遞歸做了優化，發現效果特别好，特來次分享！

首先來看看普通的遞歸算法

public static long fid(long n){
	if(n==1 || n==2) return 1;
	else return fid(n-2)+fid(n-1);
}
           

這個算法仔細分析分析會發現他的時間複雜度會随着n的增加會成指數上升，導緻在50左右計算機算起來就很吃力了！！！其原因在于算前一項所用的n-1，在算後一項所用的n-2遞歸計算了兩次，進而增加了其複雜度

再來看看優化後的遞歸算法

public static long  better_fid(int n, long result[], int len){
	len++;
	if(n==1) return 0;
	if(n>=2) result[len]=result[len-1]+result[len-2];
	return better_fid(n-1,result,len);
}

public static void better_fid_test(){
	long result[] = new long[200];
	result[0]=1;
	result[1]=1;
	int len = 1;
	System.out.println();
	System.out.println("開始進行優化後的斐波那契測試");
	System.out.println("輸入>=2的數：");
	int n = sc.nextInt();
	long start=System.nanoTime();
	better_fid(n,result,len);
	long after=System.nanoTime();
	System.out.println("第"+n+"個斐波那契數為："+result[n-1]);
	System.out.println("優化後的斐波那契的時間為5"+(after-start)+"納秒");
}
           

這個算法在我測試的時候發現，在n=15左右之前，比普通的遞歸要高，而它在n>15後，運算效果就非常好了，在n=100也是非常快的計算出來！

測試

package recurrence;
import java.util.Scanner;

public class recurrence {

private static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
	fid_test();
	better_fid_test();
}


public static long fid(long n){
	if(n==1 || n==2) return 1;
	else return fid(n-2)+fid(n-1);
}

public static void fid_test(){
	System.out.println("開始進行斐波那契測試");
	System.out.println("輸入>=2的數：");
	long n = sc.nextLong();
	long start=System.nanoTime();
	long result = fid(n);
	long after=System.nanoTime();
	System.out.println("第"+n+"個斐波那契數為："+result);
	System.out.println("優化後的斐波那契的時間為"+(after-start)+"納秒");
}


public static long  better_fid(int n, long result[], int len){
	len++;
	if(n==1) return 0;
	if(n>=2) result[len]=result[len-1]+result[len-2];
	return better_fid(n-1,result,len);
}

public static void better_fid_test(){
	long result[] = new long[200];
	result[0]=1;
	result[1]=1;
	int len = 1;
	System.out.println();
	System.out.println("開始進行優化後的斐波那契測試");
	System.out.println("輸入>=2的數：");
	int n = sc.nextInt();
	long start=System.nanoTime();
	better_fid(n,result,len);
	long after=System.nanoTime();
	System.out.println("第"+n+"個斐波那契數為："+result[n-1]);
	System.out.println("優化後的斐波那契的時間為5"+(after-start)+"納秒");
}

}
           

這裡的資料就非常明顯了！！！