面试题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上:点我前往