每天一個算法之fibonacci遞歸法優化

public class fibonacci {
         publicstatic void main(String args[]){
                   longt1=System.nanoTime();
                   longn1=recursion(40);
                   longt2=System.nanoTime();
                   longn2=circulation(40);
                   longt3=System.nanoTime();
                   System.out.println("result:"+n1+"----time:"+(t2-t1));
                   System.out.println("result:"+n2+"----time:"+(t3-t2));
         }
         //recursionis very clear.but,this method has high complexity,100 we can not caculate theresult.
         publicstatic long recursion(long n){
                   if(n<=0)return0;
                   if(n==1)return1;
                   returnrecursion(n-1)+recursion(n-2);    
         }
         publicstatic long circulation(long n){
                   if(n<2)returnn;
                   longn0=0;long n1=1;
                   longsum=0;
                   for(longi=2;i<=n;i++){
                            sum=n0+n1;
                            n0=n1;
                            n1=sum;
                   }
                   returnsum;
         }
}
           

n=10

result:55----time:6736

result:55----time:1283

n=20

result:6765----time:281608

result:6765----time:1604

n=30

result:832040----time:8039639

result:832040----time:8660

n=40

result:102334155----time:967186178

result:102334155----time:12509

n=50

第一個就算不出來了

第一個函數的執行對第二個函數的執行會有不小的影響。注釋掉第一個函數的，第二個函數運作時間會更短，不過這個結果足夠說明遞歸在有些時候是不适合的。

                  f(10)

               /        \

            f(9)         f(8)

          /     \       /    \

       f(8)     f(7)  f(7)   f(6)

      /   \     /   \ 

   f(7)  f(6)  f(6) f(5)

第一個函數之是以慢是因為裡面有重複計算的值，第二個函數正是克服了這種缺點。

這還不是最快的方法。下面介紹一種時間複雜度是O(logn)的方法。在介紹這種方法之前，先介紹一個數學公式：

通過數學歸納法可以證明

實作這種方式時，首先需要定義一個2×2的矩陣，并且定義好矩陣的乘法以及乘方運算，就可以計算了。