问答题
斐波那契数列Fn定义如下：F0=0，F1=1，Fn=Fn-1+Fn-2，n=2，3，…就此斐波那契数列，回答下列问题。
问答题
在递归计算Fn时，需要对较小的Fn-1，Fn-2，…，F1，F0精确计算多少次?
【正确答案】从题中可知：F
0=0，F
1=1，F
2=1，F
3=2，F
4=3，F
5=5，F
6=8，…
F
n=F
n-1+F
n-2 =2F
n-2+F
n-3(即F
3F
n-2+F
2F
n-3)
=3F
n-3+2F
n-4(即F
4F
n-3+F
3F
n-4)
=5F
n-4+3F
n-5(即F
5F
n-4+F
4F
n-5)
[*]
=F
n-1F
1+F
n-2F
0 归纳起来，在递归计算F
n时，需要对较小的F
n-1计算1(即F
2)次，F
n-2计算2(即F
3)次，…，F
1计算F
n次，F
0计算F
n-1次。
以计算F
5为例，其递归调用树如图所示。从图中可以看到，F
4计算1次，F
3计算2次，F
2计算3次，F
1计算F
5(=5)次，F
0计算F
4(=3)次。
[*]
【答案解析】
问答题
如果用大O表示法，递归计算Fn时递归函数的时间复杂度是多少?
【正确答案】设计算Fn的时间复杂度为T(n)，有
T(n)=T(n-1)+T(n-2)＜2T(n-1)
＜22T(n-2)
[*]
＜2nT(0)
=O(2n)
又有
T(n)=T(n-1)+T(n-2)
＞2T(n-2)
＞22T(n-4)
[*]
＞2n/2T(1)(n为奇数时；或2n/2T(0)，n为偶数时)
即
T(n)＞O(2n/2)
则
O(2n/2)＜T(n)＜O(2n)
取最坏情况上限，即T(n)=O(2n)。
【答案解析】