????????有一個(gè)大家都很熟悉的經(jīng)典數(shù)學(xué)問(wèn)題，即斐波那契數(shù)列算法問(wèn)題洪碳。這個(gè)經(jīng)典案例在算法中又會(huì)變成什么樣子呢洲炊？
int fib(int n){?
????if(n?==?0)
????????return 0;
????if(n?==?1)
????????return 1;
????return fib(n - 1)+fib(n - 2);
}
? ? ? ? 首先这刷，我們很容易使用遞歸算法來(lái)設(shè)計(jì)該算法。但是計(jì)算出結(jié)果是一個(gè)指數(shù)階的算法砌些，當(dāng)n到100的時(shí)候，每多算一個(gè)斐波那契數(shù)需要至少多算一年加匈。
? ? ? ? 那我們今天就主要介紹一下優(yōu)化后的算法存璃。
????????算法優(yōu)化1:每次記錄前兩項(xiàng)的值，只需要一次加法運(yùn)算得到當(dāng)前項(xiàng)雕拼，算法時(shí)間復(fù)雜度降低到了O（n）纵东，效率大幅度提高。
????????算法改進(jìn)2:使用迭代法啥寇，兩數(shù)輾轉(zhuǎn)相加，每次記錄前一項(xiàng)，時(shí)間復(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;
}
????????算法改進(jìn)3:接下來(lái)我們來(lái)看看對(duì)數(shù)階的斐波那契數(shù)列算法。先來(lái)看下面這種算法：
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ǔ)的值賦給b，通過(guò)觀察可以發(fā)現(xiàn)邓线，從1和0開(kāi)始將規(guī)則反復(fù)應(yīng)用n次淌友，將產(chǎn)生一對(duì)數(shù)fib(n)和fib(n+1),現(xiàn)在將這種規(guī)則看成a = bq + aq + a*pb = bp + aq其中p=0,q=1把這種變換稱(chēng)為T(mén)變換，
Tpq 變換有個(gè)特性是 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);
}
這樣的算法時(shí)間復(fù)雜度可以達(dá)到對(duì)數(shù)階。大幅地提高了算法的效率缩歪。
