面试题9：斐波那契数列

题目一：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：

$$f(n)=\begin{cases}0 & &{n=0} \\ 1 & &{n=1} \\ f(n-1)+f(n-2) & &{n>1} \end{cases} $$

分析

根据上述公式，我们可以很容易地写出如下递归代码：

long long Fib(int x)
{
    if(x==0 || x==1)
        return x;
    return Fib(x-1)+Fib(x-2);
}

不过递归方式的时间复杂度是 $O(2^n)$，空间复杂度都是是 $O(n)$，增长地很厉害，用来解释递归原理还可以，是无法应用的实际中去的。

那我们就可以把递归改成循环，使时间复杂度降到 $O(n)$。

代码如下

long long Fib(int x)
{
    if(x<=1)
        return x;
    int a=0,b=1,res;
    int i;
    for(i=0;i<x-1;++i)
    {
        res=a+b;
        a=b;
        b=res;
    }
    return res;
}

一般到这里就可以了，但我们现在有一个时间复杂度为 $O(\log N)$ 的方法，讲解如下：

有一个数学公式(设 $f(n)$ 为斐波那契数列的第 $n$ 项值)：

$$\left[\begin{matrix} f(n) & f(n-1) \\ f(n-1) & f(n-2) \end{matrix} \right] = {\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right]}^{n-1}$$

这个公式在此不做证明，有兴趣的读者可以自己用数学归纳法试着证明一下。

现在我们就将斐波那契问题转化矩阵乘法的问题了。但如果还是以普通乘法来计算的话，时间复杂度甚至比循环方法还要高。所以需要对其优化。

1. 对于矩阵乘方，常规算法需要 $O(n^3)$ 时间，《算法导论》上介绍了一种 Strassen 算法，可以将计算的时间复杂度压缩到 $O(n^{\lg 7})$，($\lg 7$ 的值在 2.80 到 2.81 之间)，在此不做验证。
2. 若 $n$ 为偶数，$a^n=a^{\frac{n}{2}}\times a^{\frac{n}{2}}$；若 $n$ 为奇数，$a^n=a \times a^{\frac{n-1}{2}}\times a^{\frac{n-1}{2}}$。所以我们可以利用乘方的这种性质来计算，时间复杂度缩减到 $O(\log N)$。

代码如下:

vector<vector<unsigned long long int> > MultiMatrix(vector<vector<unsigned long long int> > matrix1,vector<vector<unsigned long long int> > matrix2)
{
    if(matrix1.size()<=0 || matrix2.size()<=0)
        return vector<vector<unsigned long long int> >();
    vector<vector<unsigned long long int> > res;
    int i,j,k;
    res.resize(matrix1.size());
    for(i=0;i<matrix1.size();++i)
    {
        res[i].resize(matrix2[0].size());
        for(j=0;j<matrix2[0].size();++j)
        {
            res[i][j]=0;
            for(k=0;k<matrix2.size();++k)
            {
                res[i][j]+=matrix1[i][k]*matrix2[k][j];
            }
        }
    }
    return res;
}

vector<vector<unsigned long long int> > calc(vector<vector<unsigned long long int> > matrix,int x)
{
    int i;
    vector<vector<unsigned long long int> > res=matrix;
    for(i=0;i<x-1;++i)
    {
        res=MultiMatrix(matrix,res);
    }
    return res;
}

unsigned long long int Fib(int x)
{
    if(x==0 || x==1)
        return x;
    vector<vector<unsigned long long int> >matrix;
    matrix.resize(2);
    matrix[0].resize(2);
    matrix[1].resize(2);
    matrix[0][0]=matrix[0][1]=matrix[1][0]=1;
    matrix[1][1]=0;
    return calc(matrix,x-1)[0][0];
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往 b/master/09_Fibonacci/main.cpp)