????????有一個大家都很熟悉的經(jīng)典數(shù)學(xué)問題，即斐波那契數(shù)列算法問題。這個經(jīng)典案例在算法中又會變成什么樣子呢？
int fib(int n){?
????if(n?==?0)
????????return 0;
????if(n?==?1)
????????return 1;
????return fib(n - 1)+fib(n - 2);
}
? ? ? ? 首先，我們很容易使用遞歸算法來設(shè)計該算法。但是計算出結(jié)果是一個指數(shù)階的算法，當(dāng)n到100的時候，每多算一個斐波那契數(shù)需要至少多算一年。
? ? ? ? 那我們今天就主要介紹一下優(yōu)化后的算法。
????????算法優(yōu)化1:每次記錄前兩項的值，只需要一次加法運算得到當(dāng)前項，算法時間復(fù)雜度降低到了O（n），效率大幅度提高。
????????算法改進2:使用迭代法，兩數(shù)輾轉(zhuǎn)相加，每次記錄前一項，時間復(fù)雜度為O（n），空間復(fù)雜度降低到了O（1）。代碼如下：
int fib(int n){
????int i , s1 = 1 , s2 = 1;
????if(n < 1)
????????return -1;
????if(n == 1 || n == 2)
????????return 1;
????for(i = 3;i <= n; i++){
????????s1 = s1 + s2;
????????s1 = s2 - s1;
????}
????return s2;
}
????????算法改進3:接下來我們來看看對數(shù)階的斐波那契數(shù)列算法。先來看下面這種算法：
int fib(int n){
????return fib_iter(1,0,n);
}
int fib_iter(a,b,count){
? ??if(count == 0)
? ??????return b;
? ??return fib_iter(a+b , a,? count - 1);
}
????????在這種算法中，我們每次遞歸都將a+b的值賦給a，把a的值賦給b，通過觀察可以發(fā)現(xiàn)，從1和0開始將規(guī)則反復(fù)應(yīng)用n次，將產(chǎn)生一對數(shù)fib(n)和fib(n+1),現(xiàn)在將這種規(guī)則看成a = bq + aq + a*pb = bp + aq其中p=0,q=1把這種變換稱為T變換，
Tpq 變換有個特性是 Tpq 的二次方等于Tp‘q’， p‘ = pp + qq , q' = 2pq + q*q
即：a = (bp+aq)p+(bq+aq+ap)q+(bq+aq+ap)p = b(2pq+q^2)+a(p^2+2pq+2q^2)
b = (bp+aq)p+(bq+aq+ap)q = b(p^2+q^2)+a(q^2+2pq)
此處p=0，q=1
int fib(int n){
????return fib_iter(1,0,0,1,n);
}
int fib_iter(int a,int b,int p,int q,int count){
????if (count == 0)
????????return b;
else? if (count%2)
????return fib_iter(b*p+a*q+a*p,b*p+a*q,p,q,count-1);
else
????return fib_iter(a,b,p*p+q*q,q*q+2*p*q,count/2);
}
這樣的算法時間復(fù)雜度可以達到對數(shù)階。大幅地提高了算法的效率。
