斐波那契数列由以下的公式定义：
$$!F_n=\begin{cases}0 & ,n=0 \\1 & ,n=1 \\F_{n-1} + F_{n-2} & ,n\geq2\end{cases}$$
1. 递归法(最慢)
时间复杂度：$$T(n)=\Omega(\varphi^n)$$指数级。
// 输出斐波那契数列下标为n的数
// (递归法，复杂度: 指数增长)
int FibonacciSequance(int n)
{
int F0 = 0;
int F1 = 1;
if (n==0)
return F0;
else if (n==1)
return F1;
else
{
return FibonacciSequance(n-1) + FibonacciSequance(n-2);
}
}2. 自底而上的方法（中等）
按顺序计算：$$F_0,F_1, F_2,\cdots,F_{n-1},F_n $$。
时间复杂度是：$$T(n)=\Theta(n)$$
// 输出斐波那契数列下标为n的数(自底向上，复杂度: theta(n))
int FibonacciSequance(int n)
{
int F0 = 0;
int F1 = 1;
if (n==0)
return F0;
else if (n==1)
return F1;
else
{
int Fi_1 = F1;
int Fi_2 = F0;
int Fi = 0;
for (int i=2; i<=n; ++i)
{
Fi = Fi_1 + Fi_2;
Fi_2 = Fi_1;
Fi_1 = Fi;
}
return Fi;
}
}3. Naive Recursive Squaring（最快，但无法实现）
使用下面的公式计算数列中的数：
$$!F_n=round(\phi^n/\sqrt5) ,n>0$$
即：$$F_n$$等于最接近$$\phi^n/\sqrt5$$的整数，其中：
$$!\phi=\frac{1+\sqrt5}{2}=1.61803\cdots$$
使用递归法计算，分析方法的时间复杂度，方法的递归公式如下：
$$!T(n)=T(n/2)+\Theta(1)$$
根绝主方法(Master method)的得到，该方法的时间复杂度：$$T(n)=\Theta(\lg{n})$$。
由于计算精度问题，此方法无法在计算机上实现。
4. Recursive Squaring（最快）
方法3中的方法速度很快但无法实现，下面的公式给出了可以实现的方法：
$$!\left[\begin{array}{cc}F_{n+1} & F_n \\F_n & F_{n-1}\end{array}\right]={\left[\begin{array}{cc}1 & 1 \\1 & 0\end{array}\right]}^n$$
上面的公式避开了方法3中的计算精度问题。使用递归法计算，分析方法的时间复杂度，方法的递归公式同3，如下：
$$!T(n)=T(n/2)+\Theta(1)$$
根据主方法可知，算法复杂度同样为：$$T(n)=\Theta(\lg{n})$$
int matBase[4] = {1, 1, 1, 0};
// 矩阵相乘
void MatrixMult22(int *A, int *B, int *AB)
{
AB[0] = A[0]*B[0] + A[1]*B[2];
AB[1] = A[0]*B[1] + A[1]*B[3];
AB[2] = A[2]*B[0] + A[3]*B[2];
AB[3] = A[2]*B[1] + A[3]*B[3];
}
// 矩阵的N次幂
void MatrixPow22(int *A, int N, int *matPow)
{
if (N==1)
{
matPow[0] = A[0];
matPow[1] = A[1];
matPow[2] = A[2];
matPow[3] = A[3];
}
else
{
if (N%2==0) // N为偶数
{
int temp[4];
MatrixPow22(A, N/2, temp);
MatrixMult22(temp, temp, matPow);
}
else // N为奇数
{
int temp1[4];
int temp2[4];
MatrixPow22(A, (N-1)/2, temp1);
MatrixMult22(temp1, temp1, temp2);
MatrixMult22(temp2, A, matPow);
}
}
}
// 输出斐波那契数列下标为n的数
// (递归平方法，复杂度: Theta(lgn))
int FibonacciSequance(int n)
{
if (n==0)
return 0;
else
{
int matPow[4];
MatrixPow22(matBase, n, matPow);
return matPow[1];
}
}