面试题9:斐波那契数列

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

无标题


分析

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

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

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

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

代码如下

{
    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(logN)的方法,讲解如下:

有一个数学公式(设f(n)为斐波那契数列的第n项值):无标题 这个公式在此不做证明,有兴趣的读者可以自己用数学归纳法试着证明一下。

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

  1. 对于矩阵乘方,常规算法需要O(n3)时间,《算法导论》上介绍了一种Strassen算法,可以将计算的时间复杂度压缩到O(nlg7)。(lg7的值在2.80到2.81之间)在此不做验证。
  2. 若n为偶数,an=an/2an/2;若n为奇数,an=aa(n-1)/2*a(n-1)/2。所以我们可以利用乘方的这种性质来计算,时间复杂度缩减到O(logN)。

代码如下:

{
    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上:点我前往