斐波那契數列算法分析
背景：
假定你有一雄一雌一對剛出生的兔子，它們在長(cháng)到一個(gè)月大小時(shí)開(kāi)始交配，在第二月結束時(shí)，雌兔子產(chǎn)下另一對兔子，過(guò)了一個(gè)月后它們也開(kāi)始繁殖，如此這般持續下去。每只雌兔在開(kāi)始繁殖時(shí)每月都產(chǎn)下一對兔子，假定沒(méi)有兔子死亡，在一年后總共會(huì )有多少對兔子？
在一月底，最初的一對兔子交配，但是還只有1對兔子；在二月底，雌兔產(chǎn)下一對兔子，共有2對兔子；在三月底，最老的雌兔產(chǎn)下第二對兔子，共有3對兔子；在四月底，最老的雌兔產(chǎn)下第三對兔子，兩個(gè)月前生的雌兔產(chǎn)下一對兔子，共有5對兔子；……如此這般計算下去，兔子對數分別是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出規律了嗎？從第3個(gè)數目開(kāi)始，每個(gè)數目都是前面兩個(gè)數目之和。這就是著(zhù)名的斐波那契（Fibonacci）數列。
有趣問(wèn)題：
1，有一段樓梯有10級臺階,規定每一步只能跨一級或兩級,要登上第10級臺階有幾種不同的走法?
答：這就是一個(gè)斐波那契數列：登上第一級臺階有一種登法；登上兩級臺階，有兩種登法；登上三級臺階，有三種登法；登上四級臺階，有五種方法……所以，1，2，3，5，8，13……登上十級，有89種。
2，數列中相鄰兩項的前項比后項的極限是多少，就是問(wèn)，當n趨于無(wú)窮大時(shí)，F(n)/F(n+1)的極限是多少？
答：這個(gè)可由它的通項公式直接得到，極限是(-1+√5)/2，這個(gè)就是所謂的黃金分割點(diǎn)，也是代表大自然的和諧的一個(gè)數字。
數學(xué)表示：
Fibonacci數列的數學(xué)表達式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
遞歸程序1：
Fibonacci數列可以用很直觀(guān)的二叉遞歸程序來(lái)寫(xiě)，用C++語(yǔ)言的描述如下：
long fib1(int n)
{
if (n <= 2)
{
return 1;
}
else
{
return fib1(n-1) + fib1(n-2);
}
}
看上去程序的遞歸使用很恰當，可是在用VC2005的環(huán)境下測試n=37的時(shí)候用了大約3s，而n=45的時(shí)候基本下樓打完飯也看不到結果……顯然這種遞歸的效率太低了??！
遞歸效率分析：
例如，用下面一個(gè)測試函數：
long fib1(int n, int* arr)
{
arr[n]++;
if (n <= 2)
{
return 1;
}
else
{
return fib1(n-1, arr) + fib1(n-2, arr);
}
}
這時(shí)，可以得到每個(gè)fib(i)被計算的次數：
fib(10) = 1 fib(9) = 1 fib(8) = 2 fib(7) = 3
fib(6) = 5 fib(5) = 8 fib(4) = 13 fib(3) = 21
fib(2) = 34 fib(1) = 55 fib(0) = 34
可見(jiàn)，計算次數呈反向的Fibonacci數列，這顯然造成了大量重復計算。
我們令T(N)為函數fib(n)的運行時(shí)間，當N>=2的時(shí)候我們分析可知：
T(N) = T(N-1) + T(N-2) + 2
而fib(n) = fib(n-1) + fib(n-2)，所以有T(N) >= fib(n)，歸納法證明可得：
fib(N) < (5/3)^N
當N>4時(shí)，fib（N）>= (3/2)^N
標準寫(xiě)法：
顯然這個(gè)O（(3/2)^N） 是以指數增長(cháng)的算法，基本上是最壞的情況。
其實(shí)，這違反了遞歸的一個(gè)規則：合成效益法則。
合成效益法則（Compound interest rule）：在求解一個(gè)問(wèn)題的同一實(shí)例的時(shí)候，切勿在不同的遞歸調用中做重復性的工作。
所以在上面的代碼中調用fib(N-1)的時(shí)候實(shí)際上同時(shí)計算了fib(N-2)。這種小的重復計算在遞歸過(guò)程中就會(huì )產(chǎn)生巨大的運行時(shí)間。
遞歸程序2：
用一叉遞歸程序就可以得到近似線(xiàn)性的效率，用C++語(yǔ)言的描述如下：
long fib(int n, long a, long b, int count)
{
if (count == n)
return b;
return fib(n, b, a+b, ++count);
}
long fib2(int n)
{
return fib(n, 0, 1, 1);
}
這種方法雖然是遞歸了，但是并不直觀(guān)，而且效率上相比下面的迭代循環(huán)并沒(méi)有優(yōu)勢。
迭代解法：
Fibonacci數列用迭代程序來(lái)寫(xiě)也很容易，用C++語(yǔ)言的描述如下：
//也可以用數組將每次計算的f(n)存儲下來(lái)，用來(lái)下次計算用（空間換時(shí)間）
long fib3 (int n)
{
long x = 0, y = 1;
for (int j = 1; j < n; j++)
{
y = x + y;
x = y - x;
}
return y;
}
這時(shí)程序的效率顯然為O（N），N = 45的時(shí)候<1s就能得到結果。
矩陣乘法：
我們將數列寫(xiě)成：
Fibonacci[0] = 0，Fibonacci[1] = 1
Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)
可以將它寫(xiě)成矩陣乘法形式：
將右邊連續的展開(kāi)就得到：
下面就是要用O(log(n))的算法計算：
顯然用二分法來(lái)求，結合一些面向對象的概念，C++代碼如下：
class Matrix
{
public:
long matr[2][2];
Matrix(const Matrix&rhs);
Matrix(long a, long b, long c, long d);
Matrix& operator=(const Matrix&);
friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)
{
Matrix ret(0,0,0,0);
ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];
ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];
ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];
ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];
return ret;
}
};
Matrix::Matrix(long a, long b, long c, long d)
{
this->matr[0][0] = a;
this->matr[0][1] = b;
this->matr[1][0] = c;
this->matr[1][1] = d;
}
Matrix::Matrix(const Matrix &rhs)
{
this->matr[0][0] = rhs.matr[0][0];
this->matr[0][1] = rhs.matr[0][1];
this->matr[1][0] = rhs.matr[1][0];
this->matr[1][1] = rhs.matr[1][1];
}
Matrix& Matrix::operator =(const Matrix &rhs)
{
this->matr[0][0] = rhs.matr[0][0];
this->matr[0][1] = rhs.matr[0][1];
this->matr[1][0] = rhs.matr[1][0];
this->matr[1][1] = rhs.matr[1][1];
return *this;
}
Matrix power(const Matrix& m, int n)
{
if (n == 1)
return m;
if (n%2 == 0)
return power(m*m, n/2);
else
return power(m*m, n/2) * m;
}
long fib4 (int n)
{
Matrix matrix0(1, 1, 1, 0);
matrix0 = power(matrix0, n-1);
return matrix0.matr[0][0];
}
這時(shí)程序的效率為O（log(N)） 。
公式解法：
在O（1）的時(shí)間就能求得到F(n)了：
注意：其中[x]表示取距離x最近的整數。
用C++寫(xiě)的代碼如下：
long fib5(int n)
{
double z = sqrt(5.0);
double x = (1 + z)/2;
double y = (1 - z)/2;
return (pow(x, n) - pow(y, n))/z + 0.5;
}
這個(gè)與數學(xué)庫實(shí)現開(kāi)方和乘方本身效率有關(guān)的，我想應該還是在O(log(n))的效率。
總結：
上面給出了5中求解斐波那契數列的方法，用測試程序主函數如下：
int main()
{
cout << fib1(45) << endl;
cout << fib2(45) << endl;
cout << fib3(45) << endl;
cout << fib4(45) << endl;
cout << fib5(45) << endl;
return 0;
}
函數fib1會(huì )等待好久，其它的都能很快得出結果，并且相同為：1134903170。
而后面兩種只有在n = 1000000000的時(shí)候會(huì )顯示出優(yōu)勢。由于我的程序都沒(méi)有涉及到高精度，所以要是求大數據的話(huà)，可以通過(guò)取模來(lái)獲得結果的后4位來(lái)測試效率與正確性。
另外斐波那契數列在實(shí)際工作中應該用的很少，尤其是當數據n很大的時(shí)候（例如：1000000000），所以綜合考慮基本普通的非遞歸O(n)方法就很好了，沒(méi)有必要用矩陣乘法。
附錄：
程序全部源碼：
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <fstream>
using namespace std;
class Matrix
{
public:
long matr[2][2];
Matrix(const Matrix&rhs);
Matrix(long a, long b, long c, long d);
Matrix& operator=(const Matrix&);
friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)
{
Matrix ret(0,0,0,0);
ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];
ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];
ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];
ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];
return ret;
}
};
Matrix::Matrix(long a, long b, long c, long d)
{
this->matr[0][0] = a;
this->matr[0][1] = b;
this->matr[1][0] = c;
this->matr[1][1] = d;
}
Matrix::Matrix(const Matrix &rhs)
{
this->matr[0][0] = rhs.matr[0][0];
this->matr[0][1] = rhs.matr[0][1];
this->matr[1][0] = rhs.matr[1][0];
this->matr[1][1] = rhs.matr[1][1];
}
Matrix& Matrix::operator =(const Matrix &rhs)
{
this->matr[0][0] = rhs.matr[0][0];
this->matr[0][1] = rhs.matr[0][1];
this->matr[1][0] = rhs.matr[1][0];
this->matr[1][1] = rhs.matr[1][1];
return *this;
}
Matrix power(const Matrix& m, int n)
{
if (n == 1)
return m;
if (n%2 == 0)
return power(m*m, n/2);
else
return power(m*m, n/2) * m;
}
//普通遞歸
long fib1(int n)
{
if (n <= 2)
{
return 1;
}
else
{
return fib1(n-1) + fib1(n-2);
}
}
/*上面的效率分析代碼
long fib1(int n, int* arr)
{
arr[n]++;
if (n <= 1)
{
return 1;
}
else
{
return fib1(n-1, arr) + fib1(n-2, arr);
}
}
*/
long fib(int n, long a, long b, int count)
{
if (count == n)
return b;
return fib(n, b, a+b, ++count);
}
//一叉遞歸
long fib2(int n)
{
return fib(n, 0, 1, 1);
}
//非遞歸方法O(n)
long fib3 (int n)
{
long x = 0, y = 1;
for (int j = 1; j < n; j++)
{
y = x + y;
x = y - x;
}
return y;
}
//矩陣乘法O(log(n))
long fib4 (int n)
{
Matrix matrix0(1, 1, 1, 0);
matrix0 = power(matrix0, n-1);
return matrix0.matr[0][0];
}
//公式法O(1)
long fib5(int n)
{
double z = sqrt(5.0);
double x = (1 + z)/2;
double y = (1 - z)/2;
return (pow(x, n) - pow(y, n))/z + 0.5;
}
int main()
{
//n = 45時(shí)候fib1()很慢
int n = 10;
cout << fib1(n) << endl;
cout << fib2(n) << endl;
cout << fib3(n) << endl;
cout << fib4(n) << endl;
cout << fib5(n) << endl;
return 0;
}
