面试题9:斐波那契数列

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

无标题


分析

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

long Fib(int x)
1
2
3
4
5
{
if(x==0 || x==1)
return x;
return Fib(x-1,count)+Fib(x-2,count);
}

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

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

代码如下

long Fib(int x)
1
2
3
4
5
6
7
8
9
10
11
12
13
{
if(x&lt;=1)
return x;
int a=0,b=1,res;
int i;
for(i=0;i&lt;x-1;++i)
{
res=a+b;
a=b;
b=res;
}
return res;
}

一般到这里就可以了,但我们现在有一个时间复杂度为O(logN)的方法,讲解如下:

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

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

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

代码如下:

long long int> > MultiMatrix(vector<vector<unsigned long long int> > matrix1,vector<vector<unsigned long long int> > matrix2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
{
if(matrix1.size()&lt;=0 || matrix2.size()&lt;=0)
return vector&lt;vector&lt;unsigned long long int&gt; &gt;();
vector&lt;vector&lt;unsigned long long int&gt; &gt; res;
int i,j,k;
res.resize(matrix1.size());
for(i=0;i&lt;matrix1.size();++i)
{
res[i].resize(matrix2[0].size());
for(j=0;j&lt;matrix2[0].size();++j)
{
res[i][j]=0;
for(k=0;k&lt;matrix2.size();++k)
{
res[i][j]+=matrix1[i][k]*matrix2[k][j];
}
}
}
return res;
}
vector&lt;vector&lt;unsigned long long int&gt; &gt; calc(vector&lt;vector&lt;unsigned long long int&gt; &gt; matrix,int x)
{
int i;
vector&lt;vector&lt;unsigned long long int&gt; &gt; res=matrix;
for(i=0;i&lt;x-1;++i)
{
res=MultiMatrix(matrix,res);
}
return res;
}
unsigned long long int Fib(int x)
{
if(x==0 || x==1)
return x;
vector&lt;vector&lt;unsigned long long int&gt; &gt;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上:点我前往