剑指Offer(七):裴波那契数列

  • 3
  • 435 °C
  • A+
所属分类:剑指Offer
摘要

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。(n<=39)

剑指Offer(七):裴波那契数列

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。(n<=39)

斐波那契数列公式为:

剑指Offer(七):裴波那契数列

1、思路

这道题递归很好写,但是存在很严重的效率问题。我们以求解f(10)为例类分析递归的求解过程。想求f(10),需要先求得f(9)和f(8)。同样,想求得f(9),需要先求的f(8)和f(7)....我们可以用树形结构来表示这种依赖关系,如下图所示:

剑指Offer(七):裴波那契数列

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

所以,使用简单的循环方法来实现。

2、代码

C++:

Python2.7:

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • avatar hello 来自天朝的朋友 谷歌浏览器 Windows 10 浙江省杭州市 电信 1

      f斐波那列公式错了。。。。

      • avatar hello 来自天朝的朋友 谷歌浏览器 Windows 10 浙江省杭州市 电信 1

        是我搞错了 。。 :oops:

          • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 江苏省 移动

            @hello 我正在思考。。我还想哪错了 :shock: