剑指Offer面试题:7.斐波那契数列

一题目:斐波那契数列二效率很低的解法很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心上述递归的解法有很严重的效

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:7.斐波那契数列此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:斐波那契数列

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:


剑指Offer面试题:7.斐波那契数列

二 效率很低的解法

  很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心

#include "stdio.h"
#include <iostream>
using namespace std;

int Fibs(int n)
{
    if (0 == n)
    {
        return 0;
    }
    else if (1 == n)
    {
        return 1;
    }
   return Fibs(n-1) + Fibs(n-2);
}

void main()
{
    cout << "斐波那契数列:" << endl;
    cout <<Fibs(0)<<" ";
    cout <<Fibs(1)<<" ";
    cout <<Fibs(2)<<" ";
    cout <<Fibs(3)<<" ";
    cout <<Fibs(4)<<" ";
    cout <<Fibs(5)<<" ";
    cout <<Fibs(6)<<" ";
    cout <<Fibs(7)<<" ";
    cout <<Fibs(8)<<" " << endl;
    return;
}

剑指Offer面试题:7.斐波那契数列

  上述递归的解法有很严重的效率问题,通过求解第10项的调用过程图来分析:

  剑指Offer面试题:7.斐波那契数列

  从上图中不难发现:在这棵树中有很多结点是重复的,而且重复的结点数会随着n的增大而急剧增加,这意味计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的

三 时间复杂度为O(n)的解法

  改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多,我们只要想办法避免重复计算就行了。这里的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)

#include "stdio.h"
#include <iostream>
using namespace std;

int Fibs(int n)
{
    int nFibs = 0;
    if (0 == n)
    {
        return 0;
    }
    else if(1 == n)
    {
        return 1;
    }
    int nSubOne = 1;  // Fibs(n-1)
    int nSubTwo = 0;  // Fibs(n-2)
    for (int i = 2; i <= n; i ++)
    {
        nFibs = nSubOne + nSubTwo;
        nSubTwo = nSubOne;
        nSubOne = nFibs;
    }

    return nFibs;
}

void main()
{
    cout << "斐波那契数列:" << endl;
    cout <<Fibs(0)<<" ";
    cout <<Fibs(1)<<" ";
    cout <<Fibs(2)<<" ";
    cout <<Fibs(3)<<" ";
    cout <<Fibs(4)<<" ";
    cout <<Fibs(5)<<" ";
    cout <<Fibs(6)<<" ";
    cout <<Fibs(7)<<" ";
    cout <<Fibs(8)<<" " << endl;
    return;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120168.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python编程规范

    1,Python编程规范>编码>注释>缩进>空格空格在Python代码中是有意义的,因为Python的语法依赖于缩进,在行首的空格称为前导空格。在这一

  • Java虚拟机(JVM)面试题(2020最新版)

    文章目录Java内存区域说一下JVM的主要组成部分及其作用?说一下JVM运行时数据区深拷贝和浅拷贝说一下堆栈的区别?队列和栈是什么?有什么区别?HotSpot虚拟机对象探秘对象的创建为对象分配内存处理并发安全问题对象的访问定位句柄访问直接指针内存溢出异常Java会存在内存泄漏吗?请简单描述垃圾收集器简述Java垃圾回收机制GC是什么?为什么要GC垃圾回收的优点和原理。并考虑2种回收机制垃圾…

  • spring boot activiti工作流_activiti工作流优缺点

    spring boot activiti工作流_activiti工作流优缺点SpringBoot集成activiti工作流(模拟请假流程)链接:https://pan.baidu.com/s/10BT_Zertm1WBBrlrdE-QWQ提取码:zsq6学习视频地址见腾讯课堂:https://ke.qq.com/course/459167其他代码都是最原始的测试activiti的api代码,整合springboot的所有代码见下图.1.pom文件<dependency><groupId…

  • pycharm,pip3安装包失败解决,DB navigator 安装「建议收藏」

    pycharm,pip3安装包失败解决,DB navigator 安装「建议收藏」https://blog.csdn.net/TyuansushiT/article/details/81836732

  • uIP协议栈分析_协议栈

    uIP协议栈分析_协议栈转载地址:http://blog.sina.com.cn/s/blog_abd39cc70101fj1f.htmluIP特性uIP协议栈往掉了完整的TCP/IP中不常用的功能,简化了通讯流程,但保存了网络通讯必须使用的协议,设计重点放在了IP/TCP/ICMP/UDP/ARP这些网络层和传输层协议上,保证了其代码的通用性和结构的稳定性。由于uIP协议栈专门为嵌进式系统而设计,因此还具有…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号