首页 > 试题广场 >

(关于斐波那契数的三个算法) 在已知n的情况下，本题...

[问答题]
(关于斐波那契数的三个算法)  在已知n的情况下，本题对计算第n个斐波那契数F,的三种算法的效率进行了比较。假定两个数的加法、减法和乘法的代价都是O(1)，与数的大小无关。
a.证明:  计算Fn的直接递归方法的运行时间为n的幂。(例如，FIB程序。)
b.试说明如何运用记忆法在O(n)的时间内计算Fn。
c.试说明如何仅用整数加法和乘法运算，  就可以在O(lg n)的时间内计算Fn。(提示:考虑矩阵
                          
和它的幂)
d.现在假设对两个β位数相加需要(β)时间，对两个β位数相乘需要(β )时间。如果这样更合理地估计基本算术运算的代价，这三种方法的运行时间又是多少?
查看答案及解析
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 255浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号