判断题 偏易
#20940

以下代码用递推法求斐波那契数列的第n 项,时间复杂度为指数级。 int fibonacci ( int n ) { if ( n == 0 ) return 0…

以下代码用递推法求斐波那契数列的第n 项,时间复杂度为指数级。

int fibonacci(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	
	int f0 = 0; // F(0)
	int f1 = 1; // F(1)
	int current;
	
	for (int i = 2; i <= n; i++) {
		current = f0+ f1; // F(n) = F(n-1) + F(n-2)
		f0 = f1;
		f1 = current;
	}
	
	return current;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析

迭代的方式计算斐波那契数列,时间复杂度为线性O(n),而不是指数级O(2^n)