我正在阅读对 fibanocci 数字程序的分析，如下所示。提到这种实现效率低下。实际上，计算 Fn 的递归调用次数是 F(n+1)。
我的问题是：“计算 Fn 的递归调用次数为 F(n+1)”是什么意思？
int F(int i)
{
if (i < 1) return 0;
if (i == 1) return 1;
return F(i-1) + F(i-2);
}
问问题
8780 次
6 回答
4
计算斐波那契数的简单实现需要 F(n+1) 次递归调用来计算数 F(n)；即计算 f(10)=55 你需要 89 次递归调用，而 89 是 F(11)。
于 2012-09-12T13:08:15.547 回答
3
如果我们要计算第 N 个斐波那契数 F(n)=F(n-1)+F(n-2) 。我们可以用迭代法和递归法来完成。如果我们用迭代方法来做
#include<stdio.h>
main()
{
int a=0,b=1,c,i,n;
//clrscr();
printf("enter the limit of series\n");
scanf("%d",&n);
if(n==0)
printf("%d\n",a);
else
printf("%d\n%d\n",a,b);
for(i=2;i<=n;i++)
{
c=a+b;
printf("%d\n",c);
a=b;
b=c;
}
}
从 i=0 迭代到 N 需要 O(n) 时间。
但是用递归方法
int F(int i)
{
if (i < 1) return 0;
if (i == 1) return 1;
return F(i-1) + F(i-2);
}
递归关系为
___________ 0 if(n<=0)
/___________ 1 if(n==1)
Fibonacci(n) ____/
\
\___________ Fibonacci(n-1)+Fibonacci(n-2)
所以我们的问题 n = (n-1) 的子问题 + (n-2) 的子问题因此我们的时间函数 T(n) 如下
T(n)=T(n-1)+T(n-2)+O(1)
T(n)={T(N-2)+T(n-3)}+T(n-2) since T(n-1)=T(n-2)+T(n-3) -------- equation(1)
from above you can see T(n-2) is calculated twice. If we expand the recursion tree for N=5 . The recursion tree is as follows
Fib(5)
|
_____________________/ \__________________
| |
Fib(4) + fib(3)
| |
_______/ \_______ ________/ \_______
| + | | + |
Fib(3) Fib(2) Fib(2) Fib(1)
| | |
_______/ \____ ____/ \_______ _______/ \_____
| + | | + | | + |
Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)
_______/ \_______
| + |
Fib(1) Fib(0)
如果我们观察递归树，我们会发现 Fib(1) 被计算了 5 次 Fib(2) 被计算了 3 次 Fib(3) 被计算了 2 次
所以使用递归我们实际上是在做冗余计算。如果您使用迭代方法，则可以避免这些多余的计算。
T(n)=T(n-1)+T(n-2)+1
来自之前的 SO 帖子斐波那契数列的计算复杂性
程序的复杂度大约等于 bigoh(2power(n)) 。由于 O(n) < O(2powerN) 递归方法效率不高。
于 2012-09-12T16:39:49.293 回答
2
“程序的复杂性大约等于 bigoh(2power(n)) 。由于 O(n) < O(2powerN) 递归方法效率不高。”
如果他们根据所需的递归调用量来计算这种复杂性，那么我不知道他们从哪里得到 2^n。该图根本不对 2^n 建模，对于较大的值，建模会显着衰减。到 832,040 的第 30 项，需要 2,692,536 次递归调用来计算它，远低于超过 10 亿的 2^30。不到1%！
于 2013-08-14T06:33:57.803 回答
0
这意味着要计算 10 个数字的斐波那契数，您需要运行递归 10+1 次才能获得它。有多种算法可以改进这个时间线。
在这里查看这篇文章，它解释了查找斐波那契数的时间复杂度及其改进：斐波那契数列的计算复杂度
于 2012-09-12T13:07:18.943 回答
0
这是我的斐波那契算法
#include<stdio.h>
main()
{
// If we walk backwards in the fibonacci series, the values before
// zero will be 1 and -1. i.e the series can be re imagined as
// -1, 1, 0, 1, 1, 2, 3.
// This will spare us from adding special handling for first
// and second element of the series
int a=-1,b=1,c,i,n;
printf("enter the limit of series\n");
scanf("%d",&n);
printf("The series is : ");
for(i=1;i<=n;i++)
{
c=a+b;
printf("%d\n",c);
// move a and b forward
a=b;
b=c;
}
}
于 2013-04-12T14:01:54.627 回答
0
这是斐波那契的一些改进版本，我们只计算一次数字的斐波那契：
dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
if (a in dicFib):
return dicFib[a]
else :
global iterations
fib = fibonacci(a-2)+fibonacci(a-1)
dicFib[a] = fib
iterations += 1
return fib
print ("fibonacci of 10 is:" , fibonacci(10))
print ("fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)
# ('fibonacci of 10 is:', 55)
# ('fibonacci of all numbers:', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# ('iterations:', 9)
在这里，我们将每个数字的斐波那契存储在字典中。所以你可以看到它每次迭代只计算一次，而对于 fibonacci(10) 它只有 9 次。
于 2017-04-09T07:38:10.223 回答