文档章节

斐波那契数列递归实现和优化

cuibin1991
 cuibin1991
发布于 2016/08/16 09:57
字数 180
阅读 2
收藏 0

递归的求解过程存在严重的效率问题,如果想得到f(10),需要先求解f(8)和f(9)。而求解f(9)又要先求解f(8)和f(7),如书中的树形结构:

输入图片说明

树中有很多重复节点,重复节点会随着n的增大而急剧增加,计算量也会随着n增大而急剧增大。

优化:从上往下计算,首先根据f(0)和f(1)算出f(2),再关键f(1)和f(2)算出f(3).....依次算法第n项。这种思路的时间复杂度是O(n)。

递归和优化的代码实现如下:http://www.oschina.net/code/snippet_1051716_58660

© 著作权归作者所有

共有 人打赏支持
cuibin1991
粉丝 2
博文 15
码字总数 2682
作品 0
房山
程序员
私信 提问
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity
2014/06/20
0
0
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
08/11
0
0
斐波那契数

一、题目: 递归和非递归分别实现求第n个斐波那契数。 二、解题思路: 先了解下斐波拉契数列 (1 1 2 3 5 8 13 21 34 55···),第n个斐波那契数等于(n-1)个斐波那契数加上(n-2)个斐波那...

qq_38646470
2017/11/13
0
0
python实现斐波那契数列

斐波那契数列的发明者是意大利数学家昂纳多.斐波那契(Leonardo Fibonacci)。斐波那契数列又被称为黄金分割数列,或兔子数列。它指的是这样一个数列:0 1 1 2 3 5 8 13 21 34 ....在数学上,...

大陌
2017/07/09
0
0
重点汇总-python-gitbook-重要点学习-4-数据结构/编程题

数据结构 - 红黑树 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;...

时间之友
2017/12/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

flutter Expanded用法

使用的地方:一个分类,类似京东的,左右两边都可以滑动 Widget build(BuildContext context) { return Row(children: [ Column( children: <Widget>[ Ex......

大灰狼wow
11分钟前
1
0
Java8 Map中新增的方法使用总结

前言 得益于 Java 8 的 default 方法特性,Java 8 对 Map 增加了不少实用的默认方法,像 getOrDefault, forEach, replace, replaceAll, putIfAbsent, remove(key, value), computeIfPresent,......

kaixin_code
21分钟前
1
0
@TransactionConfiguration

@TransactionConfiguration过时与替代写法 @TransactionConfiguration 替代写法

miaojiangmin
23分钟前
0
0
浅谈Vue响应式(数组变异方法)

很多初使用Vue的同学会发现,在改变数组的值的时候,值确实是改变了,但是视图却无动于衷,果然是因为数组太高冷了吗? 查看官方文档才发现,不是女神太高冷,而是你没用对方法。 看来想让女...

开元中国2015
24分钟前
1
0
Elasticsearch通关教程(五):如何通过SQL查询Elasticsearch

  这篇博文本来是想放在全系列的大概第五、六篇的时候再讲的,毕竟查询是在索引创建、索引文档数据生成和一些基本概念介绍完之后才需要的。当前面的一些知识概念全都讲解完之后再讲解查询是...

SEOwhywhy
43分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部