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項。

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

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

　　// 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(10)作為例子來分析遞歸求解的過程。要求得f(10)，需要求得f(9)和f(8)。同樣，要求得f(9)，要先求得f(8)和f(7)……我們用樹形結構來表示這種依賴關系

　　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ù)會隨著n的增大而急劇增加。這意味這計算量會隨著n的增大而急劇增大。事實上，用遞歸方法計算的時間復雜度是以n的指數(shù)的方式遞增的。大家可以求Fibonacci的第100項試試，感受一下這樣遞歸會慢到什么程度。在我的機器上，連續(xù)運行了一個多小時也沒有出來結果。

　　其實改進的方法并不復雜。上述方法之所以慢是因為重復的計算太多，只要避免重復計算就行了。比如我們可以把已經得到的數(shù)列中間項保存起來，如果下次需要計算的時候我們先查找一下，如果前面已經計算過了就不用再次計算了。

　　更簡單的辦法是從下往上計算，首先根據(jù)f(0)和f(1)算出f(2)，在根據(jù)f(1)和f(2)算出f(3)……依此類推就可以算出第n項了。很容易理解，這種思路的時間復雜度是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;

　　}

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

　　{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)}表示一個矩陣。在矩陣中第一行第一列是f(n+1)，第一行第二列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)

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

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

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

　　2015軟件水平考試《程序員》知識點總結匯總