O(logn)求Fibonacci數(shù)列

　　題目：定義Fibonacci數(shù)列如下：

　　/ 0 n=0

　　f(n)= 1 n=1

　　\ f(n-1)+f(n-2) n=2

　　輸入n，用最快的方法求該數(shù)列的第n項(xiàng)。

　　分析：在很多C語(yǔ)言教科書(shū)中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fibonacci作為例子。因此很多程序員對(duì)這道題的遞歸解法非常熟悉，看到題目就能寫(xiě)出如下的遞歸求解的代碼。

　　///////////////////////////////////////////////////////////////////////

　　// Calculate the nth item of Fibonacci Series recursively

　　///////////////////////////////////////////////////////////////////////

　　long long Fibonacci_Solution1(unsigned int n)

　　{

　　int result[2] = {0, 1};

　　if(n < 2)

　　return result[n];

　　return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);

　　}

　　但是，教科書(shū)上反復(fù)用這個(gè)題目來(lái)講解遞歸函數(shù)，并不能說(shuō)明遞歸解法最適合這道題目。我們以求解f(10)作為例子來(lái)分析遞歸求解的過(guò)程。要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和f(7)……我們用樹(shù)形結(jié)構(gòu)來(lái)表示這種依賴關(guān)系

　　f(10)

　　/ \

　　f(9) f(8)

　　/ \ / \

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

　　/ \ / \

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

　　我們不難發(fā)現(xiàn)在這棵樹(shù)中有很多結(jié)點(diǎn)會(huì)重復(fù)的，而且重復(fù)的結(jié)點(diǎn)數(shù)會(huì)隨著n的增大而急劇增加。這意味這計(jì)算量會(huì)隨著n的增大而急劇增大。事實(shí)上，用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以n的指數(shù)的方式遞增的。大家可以求Fibonacci的第100項(xiàng)試試，感受一下這樣遞歸會(huì)慢到什么程度。在我的機(jī)器上，連續(xù)運(yùn)行了一個(gè)多小時(shí)也沒(méi)有出來(lái)結(jié)果。

　　其實(shí)改進(jìn)的方法并不復(fù)雜。上述方法之所以慢是因?yàn)橹貜?fù)的計(jì)算太多，只要避免重復(fù)計(jì)算就行了。比如我們可以把已經(jīng)得到的數(shù)列中間項(xiàng)保存起來(lái)，如果下次需要計(jì)算的時(shí)候我們先查找一下，如果前面已經(jīng)計(jì)算過(guò)了就不用再次計(jì)算了。

　　更簡(jiǎn)單的辦法是從下往上計(jì)算，首先根據(jù)f(0)和f(1)算出f(2)，在根據(jù)f(1)和f(2)算出f(3)……依此類推就可以算出第n項(xiàng)了。很容易理解，這種思路的時(shí)間復(fù)雜度是O(n)。

　　///////////////////////////////////////////////////////////////////////

　　// Calculate the nth item of Fibonacci Series iteratively

　　///////////////////////////////////////////////////////////////////////

　　long long Fibonacci_Solution2(unsigned n)

　　{

　　int result[2] = {0, 1};

　　if(n < 2)

　　return result[n];

　　long long fibNMinusOne = 1;

　　long long fibNMinusTwo = 0;

　　long long fibN = 0;

　　for(unsigned int i = 2; i <= n; ++ i)

　　{

　　fibN = fibNMinusOne + fibNMinusTwo;

　　fibNMinusTwo = fibNMinusOne;

　　fibNMinusOne = fibN;

　　}

　　return fibN;

　　}

　　這還不是最快的方法。下面介紹一種時(shí)間復(fù)雜度是O(logn)的方法。在介紹這種方法之前，先介紹一個(gè)數(shù)學(xué)公式：

　　{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1

　　(注：{f(n+1), f(n), f(n), f(n-1)}表示一個(gè)矩陣。在矩陣中第一行第一列是f(n+1)，第一行第二列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)

　　有了這個(gè)公式，要求得f(n)，我們只需要求得矩陣{1, 1, 1,0}的n-1次方，因?yàn)榫仃噞1, 1, 1,0}的n-1次方的結(jié)果的第一行第一列就是f(n)。這個(gè)數(shù)學(xué)公式用數(shù)學(xué)歸納法不難證明。感興趣的朋友不妨自己證明一下。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識(shí)點(diǎn)總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識(shí)點(diǎn)總結(jié)匯總