首页 > 试题广场 >

斐波那契数列的定义如下：F1 = 1, F2 = 1, Fn

[单选题]

斐波那契数列的定义如下：F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 (n ≥ 3)。如果用下面的函数计算斐波那契数列的第 n 项，则其时间复杂度为（）。

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

查看正确选项

Low-key-GJR

mdzz，看到网上这道题的sb题解后我佛了。。。

设T(n)表示计算F(n)的时间复杂度，那么T(n)=T(n-1)+T(n-2)

T(1)=T(2)=1

所以T(n)=F(n)

发表于 2019-10-14 20:49:06 回复(0)

提交观点

问题信息

提高 C++ Pascal 数学

来自：NOIP2013初赛提高组

上传者：牛客309901号

难度：

1条回答 0收藏 5438浏览

扫一扫，把题目装进口袋