斐波那契数列递归算法 和非递归算法 时间复杂度各是多少 给出详细的解析
时间: 2023-08-22 21:17:46 浏览: 78
斐波那契数列是指每个数都是前两个数之和的数列,第一个和第二个数分别是 0 和 1。数列从第三项开始,每一项都等于前两项之和。即
0, 1, 1, 2, 3, 5, 8, 13, 21...
递归算法:
斐波那契数列递归算法实现比较简单,代码如下:
```python
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
```
这个递归算法的时间复杂度为 $O(2^n)$,因为每个数都要被计算一次,而每个数都需要调用两次函数。
非递归算法:
非递归算法使用循环来计算斐波那契数列,代码如下:
```python
def fibonacci_iterative(n):
if n <= 1:
return n
else:
a, b = 0, 1
for i in range(n-1):
a, b = b, a + b
return b
```
这个非递归算法的时间复杂度为 $O(n)$,因为每个数只需要被计算一次,而且循环的次数也是 $n$ 次。
因此,为了获得更高效的计算结果,我们应该使用非递归算法来计算斐波那契数列。
相关问题
用c语言实现斐波那契数列的递归算法和非递归算法,并给出这两个算法的时间复杂度
好的,下面是用C语言实现斐波那契数列的递归算法和非递归算法,并给出它们的时间复杂度。
1. 递归算法:
```c
#include <stdio.h>
int fibonacci_recursive(int n) {
if (n <= 1)
return n;
else
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}
int main() {
int n;
printf("请输入要计算斐波那契数列的项数:");
scanf("%d", &n);
printf("斐波那契数列的第%d项为:%d\n", n, fibonacci_recursive(n));
return 0;
}
```
递归算法的时间复杂度为指数级别的 O(2^n)。
2. 非递归算法:
```c
#include <stdio.h>
int fibonacci_iterative(int n) {
if (n <= 1)
return n;
int prev = 0;
int curr = 1;
int result = 0;
for (int i = 2; i <= n; i++) {
result = prev + curr;
prev = curr;
curr = result;
}
return result;
}
int main() {
int n;
printf("请输入要计算斐波那契数列的项数:");
scanf("%d", &n);
printf("斐波那契数列的第%d项为:%d\n", n, fibonacci_iterative(n));
return 0;
}
```
非递归算法的时间复杂度为线性级别的 O(n)。
总结:
- 递归算法的时间复杂度为 O(2^n),随着 n 的增大,计算时间呈指数级增长,效率较低。
- 非递归算法的时间复杂度为 O(n),随着 n 的增大,计算时间呈线性增长,效率较高。
C语言分别编写出斐波那契数列的递归和非递归算法并分别求时间和空间复杂度
递归算法:
```c
int fibonacci_recursive(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}
}
```
时间复杂度:O(2^n),空间复杂度:O(n)
非递归算法:
```c
int fibonacci_nonrecursive(int n) {
if (n <= 1) {
return n;
} else {
int prev = 0, curr = 1, result;
for (int i = 2; i <= n; i++) {
result = prev + curr;
prev = curr;
curr = result;
}
return result;
}
}
```
时间复杂度:O(n),空间复杂度:O(1)