简单推断一下,当n>2时,递归调用的次数call_fab(n) = 2*fab(n) - 1,再简单证明一下。
用call_fab(n)代表递归调用的次数
n = 3时,调用fab(3),会递归调用fab(1)和fab(2),而fab(1)和fab(2)只需要调用一次,加上本身一次,一共调用3次,而fab(3) = 2,3 = 2 * 2 - 1,满足推断
n = 4时,fab(4) = fab(3) + fab(2),所以call_fab(4) = 1 + call_fab(3) + call_fab(2) = 5
fab(4) = 3,满足5 = 3 * 2 - 1
同理n=5也可以简单计算得出,这样我有连续3个结果,作为归纳法证明的基础
假设n = k(k >= 5)成立,即
fab(k) = fab(k-2) + fab(k - 1),有call_fab(k) = 2fab(k) - 1
那么当n=k+1时,fab(k+1) = fab(k - 1) + fab(k),
call_fab(k+1) = 1 + call_fab(k - 1) + call_fab(k) = 1 + 2fab(k-1) - 1 + 2fab(k) - 1
= 2(fab(k-1) + fab(k)) - 1 = 2fab(k+1) - 1,归纳法得证。
所以,对于大于2的整数n,其斐波那契数列递归算法的调用次数为2*n的斐波那契数列值 - 1,故答案是D,时间复杂度和该数列是一致的。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。