1.遞回方式
public static void main(String[] args) { long start=System.currentTimeMillis(); System.out.println(start); System.out.println(fibonacci(50)); long end=System.currentTimeMillis(); System.out.println(end); System.out.println("用時："+(end-start)+"ms"); } public static double fibonacci(int n){ if(n==0){ return 0; } if(n==1){ return 0; } if(n==2){ return 1; } return fibonacci(n-2)+fibonacci(n-1); }
可以看到遞回的方式，效率非常低，非常耗時，而且求大一點的數的時候，可能會直接溢位
2. 動態規劃
public static void main(String[] args) { long start=System.currentTimeMillis(); System.out.println(start); System.out.println(fibonacci(50)); long end=System.currentTimeMillis(); System.out.println(end); System.out.println("用時："+(end-start)+"ms"); } public static double fibonacci(int n){ if(n==0){ return 0; } double [] temp=new double[n]; temp[0]=0; temp[1]=1; if(n>1){ for(int i=2;i<n;i++){ temp[i]=temp[i-1]+temp[i-2]; } } return temp[n-1]; }
對比一下，動態規劃的效率比遞回快了不止一個量級
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51496.html
標籤：其他
上一篇：隨機生成九宮格圖形密碼-實作