时间复杂度:
兔子数列
假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永远不死去……那么,由1对初生兔子开始,12个月后会有多少对兔子?
问题分析
太常见的题目了,就不一一每月举例分析了。
这个数列有明显的特点,从第3个月开始,当月的兔子数=上月兔子数+当月新生兔子数,而当月新生的兔子正好是上上月的兔子数。因此,易得
当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下:1,1,2,3,5,8,13,21,34,……
递归表达式:
算法1(按照递归表达式设计):
long long Fib1(int n)
{
if( n<1 ) return -1;
if( n==1 || n==2 ) return 1;
return Fib1(n-1)+Fib1(n-2);
}
算法复杂度分析:
假设T(n)表示计算Fib1(n)所需要的基本操作次数,那么:
n=1时,T(n)=1;
n=2时,T(n)=1;
n=3时,T(n)=3;//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1)
n>2时,T(n)=T(n-1)+T(n-2)+1;
递归表达式和时间复杂度T(n)之间的关系如下:
由此可得:T(n)>=F(n)
又斐波那契数列通项为:
当n趋近于无穷时,
发现这里的时间复杂度属于爆炸增量函数
算法2(记录前两项的值):
long long Fib2(int n)
{
if( n<1 ) return -1;
int * a = new int[n+1];//定义一个长度为n+1的数组,0空间未使用
a[1] = 1;
a[2] = 1;
for(int i=3;i<=n;++i)
a[i] = a[i-1]+a[i-2];
return a[n];
}
算法复杂度分析:
时间复杂度为O(n),从原来的指数阶降到了多项式阶
空间复杂度为O(n)
但我们需要得到第n个斐波那契数,中间结果只是为了下一次使用,根本不需要记录。因此,我们可以在改进算法。
算法3(迭代法):
long long Fib3(int n)
{
int s1,s2;
if( n<1 ) return -1;
if( n==1 || n==2 ) return 1;
s1 = 1;
s2 = 1;
for(int i=3;i<=n;++i)
{
s2 += s1;//辗转相加法
s1 = s2-s1;//记录前一项
}
return s2;
}
初始值: | 当前解 | 记录前一项 |
---|---|---|
i=3时 | ||
i=4时 | ||
i=5时 | ||
i=6时 | ||
…… | …… | …… |
算法使用了若干个辅助变量,迭代辗转相加,每次记录前一项,时间复杂度为O(n),但空间复杂度降到了O(1)。
但其实斐波那契数列时间复杂度还可以降到对数阶O(logn)。
算法4(利用矩阵的乘法):
数学基础推导先写在这里,由于博主本人代码能力还不过关,后期会补上矩阵代码:
计算f(n)即计算,而计算矩阵的(n-2)次方,又可以进行分解,即计算的平方,逐步分解下去;由于折半计算矩阵的次方,因而时间复杂度为O(logn) 。
参考文献:
[1] 陈小玉.趣学算法[M].北京:人民邮电出版社,2017:11-14.
[2] beautyofmath.关于斐波那契数列三种解法及时间复杂度分析[EB/OL].https://blog.csdn.net/beautyofmath/article/details/48184331, 2015-09-02/2019-02-01.
[2] ECJTU_ACM_余伟伟.斐波那契数列算法及时间复杂度分析[EB/OL].https://blog.csdn.net/ecjtu_yuweiwei/article/details/47282457, 2015-08-04/2019-02-01.