2. 公务员
  3. 斐波那契数列Fn定义如下： F0=0， F1=1， Fn=Fn-1+Fn-2， n=2，3，… 请就此斐波那契数列回答下列问题： (1)在递归计算Fn时，需要对较小的Fn-1，Fn-2，…，F1，Fn精确计算多少次?

斐波那契数列Fn定义如下： F0=0， F1=1， Fn=Fn-1+Fn-2， n=2，3，… 请就此斐波那契数列回答下列问题： (1)在递归计算Fn时，需要对较小的Fn-1，Fn-2，…，F1，Fn精确计算多少次?

admin2013-12-19  31
问题 斐波那契数列Fn定义如下：
    F0=0，  F1=1，  Fn=Fn-1+Fn-2，  n=2，3，…
    请就此斐波那契数列回答下列问题：
    (1)在递归计算Fn时，需要对较小的Fn-1，Fn-2，…，F1，Fn精确计算多少次?
    (2)如果用大O表示法，试给出递归计算Fn时，递归函数的时间复杂度为多少?
选项
答案(1)由斐波那契数列的定义可得： Fn=Fn-1+Fn-2 =2Fn-2+Fn-2 =3Fn-3+2Fn-4 =5Fn-4+3Fn-5 =8Fn-5+5Fn-6 =pF1+qF0 设Fm的执行次数为Bm(m=0，1，2，…，n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行再次，即Bn-2=2；直至F1被执行p次，F0被执行q次，即B0=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得：[*] (2)时间复杂度为O(n)。
解析 本题主要考查递归算法的时间复杂度。考生应该比较熟悉斐波那契数列，只要具备一定的数学功底，解决该题应该没有什么困难。但是，通过该题需要掌握将实际问题转换成数据结构，进而能够通过数学分析得到时间复杂度的能力。
转载请注明原文地址:https://kaotiyun.com/show/eSal777K
本试题收录于： 计算机专业知识题库事业单位考试分类
0

计算机专业知识

事业单位考试

相关试题推荐
随机试题
最新回复(0)