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語言教科書中講到遞歸函數(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);
}
但是,教科書上反復(fù)用這個題目來講解遞歸函數(shù),并不能說明遞歸解法最適合這道題目。我們以求解f(10)作為例子來分析遞歸求解的過程。要求得f(10),需要求得f(9)和f(8)。同樣,要求得f(9),要先求得f(8)和f(7)……我們用樹形結(jié)構(gòu)來表示這種依賴關(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)在這棵樹中有很多結(jié)點(diǎn)會重復(fù)的,而且重復(fù)的結(jié)點(diǎn)數(shù)會隨著n的增大而急劇增加。這意味這計(jì)算量會隨著n的增大而急劇增大。事實(shí)上,用遞歸方法計(jì)算的時間復(fù)雜度是以n的指數(shù)的方式遞增的。大家可以求Fibonacci的第100項(xiàng)試試,感受一下這樣遞歸會慢到什么程度。在我的機(jī)器上,連續(xù)運(yùn)行了一個多小時也沒有出來結(jié)果。
其實(shí)改進(jìn)的方法并不復(fù)雜。上述方法之所以慢是因?yàn)橹貜?fù)的計(jì)算太多,只要避免重復(fù)計(jì)算就行了。比如我們可以把已經(jīng)得到的數(shù)列中間項(xiàng)保存起來,如果下次需要計(jì)算的時候我們先查找一下,如果前面已經(jīng)計(jì)算過了就不用再次計(jì)算了。
更簡單的辦法是從下往上計(jì)算,首先根據(jù)f(0)和f(1)算出f(2),在根據(jù)f(1)和f(2)算出f(3)……依此類推就可以算出第n項(xiàng)了。很容易理解,這種思路的時間復(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;
}
這還不是最快的方法。下面介紹一種時間復(fù)雜度是O(logn)的方法。在介紹這種方法之前,先介紹一個數(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)}表示一個矩陣。在矩陣中第一行第一列是f(n+1),第一行第二列是f(n),第二行第一列是f(n),第二行第二列是f(n-1)。)
有了這個公式,要求得f(n),我們只需要求得矩陣{1, 1, 1,0}的n-1次方,因?yàn)榫仃噞1, 1, 1,0}的n-1次方的結(jié)果的第一行第一列就是f(n)。這個數(shù)學(xué)公式用數(shù)學(xué)歸納法不難證明。感興趣的朋友不妨自己證明一下。
相關(guān)推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |