复杂度分析之斐波那契数列数列定义函数式时间复杂度空间复杂度疑问解析参考资料

133 阅读 0 评论 88 点赞

我是靠谱客的博主忐忑小笼包，这篇文章主要介绍复杂度分析之斐波那契数列数列定义函数式时间复杂度空间复杂度疑问解析参考资料，现在分享给大家，希望可以做个参考。

数列定义

英文名叫Fibonacci sequence，翻译过来就是斐波那契数列，其特点如下:0 1 1 2 3 5 8 ...，简单归纳就是F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

函数式

常见的代码表达式采用递归，如下所示

复制代码

1
2
3
4
int f(int n){
	if( n <= 1 ) return n;
	else return f(n-1)+f(n-2);
}

时间复杂度

此函数较复杂，无法直接看出，假设n对应复杂度T(n)，由于if( n <= 1 )执行1次，f(n-1)执行1次，f(n-2)执行1次，然后f(n-1)和f(n-2)执行一次，因此有T(n)=T(n-1)+T(n-2)+4，忽略次要项，得到T(n)=T(n-1)+T(n-2)，根据数学知识可得通项式为