开发者社区> 问答> 正文

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

A:O(logN)B:O(N)C:O(N!)D:O(FN)

展开
收起
知与谁同 2018-07-16 13:16:12 3690 0
2 条回答
写回答
取消 提交回答
  • TA有点害羞,没有介绍自己...
    B
    附加:当使用{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1,求解释,会将时间复杂度减为A
    2019-07-17 22:54:01
    赞同 展开评论 打赏
  • 静静的看着你们
    long fab(long n)
    {
        if (n < 2) return 1;
        return fab(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,时间复杂度和该数列是一致的。

    2019-07-17 22:54:01
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
“大数据+算法”助力B2B未来商业 立即下载
数据+算法定义新世界 立即下载
Apache Flink 流式应用中状态的数据结构定义升级 立即下载