当前位置:首页 » 操作系统 » 斐波那契数列的递归算法

斐波那契数列的递归算法

发布时间: 2024-05-04 14:34:55

⑴ [数据结构与算法分析]斐波那契数列递归算法时间复杂度为多少

longfab(longn)
{
if(n<2)return1;
returnfab(n-1)+fab(n-2);
}

简单推断一下,当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,时间复杂度和该数列是一致的。

热点内容
两麦分离算法 发布:2025-04-04 11:23:45 浏览:427
换一个浏览器ftp打不开 发布:2025-04-04 11:23:44 浏览:180
雅奇sql 发布:2025-04-04 11:13:31 浏览:681
安卓手机怎么样拍摄电影 发布:2025-04-04 11:12:24 浏览:162
如何盗取苹果手机截屏密码 发布:2025-04-04 11:10:51 浏览:155
怎么自己写个简单的安卓软件 发布:2025-04-04 11:10:05 浏览:431
外派管理员密码在哪里 发布:2025-04-04 11:02:07 浏览:522
阿里云服务器与基站 发布:2025-04-04 10:56:19 浏览:69
服务器版开票系统地址怎么更改 发布:2025-04-04 10:39:10 浏览:1000
vb绑定数据库 发布:2025-04-04 10:36:52 浏览:806