以下计算斐波那契数列的函数时间复杂度为() 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)

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

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)
```

还没有评论

举报纠错

切换

1 个答案

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 项试试，感受一下这样递归会慢到什么程度。在我的机器上，连续运行了一个多小时也没有出来结果。

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目