首页 > 试题广场 >

以下计算斐波那契数列的函数时间复杂度为()

[单选题]

int Fibonacci(int n)
{
   if(n==0)
     return 0;
   else if(n==1)
     return 1;
   else
     return Fibonacci(n-1)+Fibonacci(n-2)
}

```
O(nlogn)
```
```
O(n^2)
```
```
O(n)
```
```
O(2^n)
```

查看正确选项

zhisheng_blog

复杂度是O(2^n)

发表于 2016-01-19 16:27:03 回复(1)

Anna8023

斐波那契数列中，任何一个数等于比它小1的数字加上比它小2的数字，所以除了最后一个和倒数第一个数，所有的数都可能成为比其他数小1，或者小2的数字，每个数字都会在计算中出现两2次，因为有n 个数，所以复杂度是O(2^n)。以上仅代表个人观点，有问题欢迎提出～～

发表于 2015-11-24 12:52:55 回复(5)

huixieqingchun

这种递归可以看成是是一棵二叉树，题目相当于是求二叉树中的总结点个数。

发表于 2016-06-05 17:39:21 回复(7)

LZY019

                   f(10)
               /    \
              f(9)    f(8)
            /    \    /   \
        f(8)       f(7)   f(7) f(6)
       /    \      /   \

f(7) f(6) f(6) f(5)

我们不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着 n 的增大而急剧增加。这意味这计算量会随着 n 的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以 n 的指数的方式递增的。大家可以求 Fibonacci 的第 100 项试试，感受一下这样递归会慢到什么程度。在我的机器上，连续运行了一个多小时也没有出来结果。

发表于 2016-02-29 12:21:53 回复(4)

拿不到offer就只是个富二代了

看了一眼讨论，没有一个是从正统计算时间复杂度的方法来解答的。这里查阅了一篇博客（推荐大家去看一下http://blog.csdn.net/beautyofmath/article/details/48184331），按正常的步骤来解答这个算法的时间复杂度：

T(0)=T(1)=1;

T(n)=T(n-1)+T(n-2);(n>1)

设f(n)为参数为n时的时间复杂度，很明显：f(n)=f(n-1)+f(n-2)
这就转化为了数学上的二阶常系数差分方程，并且为其次方程。
即转化为了求f(n)的值，f(n)=f(n-1)+f(n-2)且f(0)=0; f(1)=1;
特征方程为：x^2-x-1=0
得 x=(1±√5)/2

因而f(n)的通解为:
这里写图片描述

由f(0)=0; f(1)=1可解得c_1，c_2
最终可得，时间复杂度为：
这里写图片描述

这个递归求斐波那契数列和的算法时间复杂度太高，还有两外两种时间复杂度分别为O(n)和O(logn)的方法。

发表于 2017-03-16 09:25:40 回复(2)

YuchaoHuang

画出递归树：
f(10)
                 /              \
              f(9)                 f(8)
            /         \             /       \
          f(8)       f(7)   f(7)      f(6)
       /    \      /     \

f(7) f(6) f(6) f(5)

计算复杂度：
2^0+2^1+2^2+.....2^n = O(2^n)

发表于 2021-02-09 23:36:06 回复(0)

52Heartz

推荐两篇文章：

发表于 2019-03-22 19:36:32 回复(0)

xxxxxxxxxxxxxxxa

我知道我为啥错了，以前我一直这么算

T(n)=T(n-1)+T(n-2)

T(n-1)=T(n-2)+T(n-3)

T(3)=T(2)+T(1)

T(n)=T(n-2)+...T(1)

然后就变成O(n^2)

这样做的错误就在于是否默认T(n)=n了、、

发表于 2018-07-01 10:16:44 回复(0)

codeforyou

这个递归数不是一个完全二叉树，边减1另一边减2，所以时间复杂度是1.6181^n

发表于 2017-03-12 17:20:07 回复(0)

装逼小王子

f(4)

               /    \
              f(3)    f(2)
            /    \ / \
        f(2)    f(1) f(1) f(0)
       /    \

f(1) f(0)

求二叉树的结点总数，假设二叉树高为x，那么结点总数由等比数列求和公式是2^x-1,然后因为f(n) = f(n-1)+f(n-2),到f(0)和f(1)的时候停止，所以树高是n层(第n层不满)，近似计算忽略常数时间复杂度O(n) = 2^n

发表于 2016-10-07 15:50:12 回复(0)

提交观点

问题信息

复杂度

来自：搜狗2016研发工程师...

上传者：SunburstRun

难度：

10条回答 404收藏 21216浏览

以下计算斐波那契数列的函数时间复杂度为()

问题信息

热门推荐

相关试题