文档章节

Fibonacci算法的三种实现与性能比较

longrmlife
 longrmlife
发布于 2013/04/18 15:56
字数 551
阅读 131
收藏 0

代码如下:

import java.util.ArrayList;
import java.util.List;

public class Fibonacci {

	/**
	 * 递归算法:不断调用自身实现深度计算
	 * @param n
	 * @return
	 */
	public static Long recursiveCompute(int n) {
		if (n <= 2)
			return 1L;
		else
			return recursiveCompute(n - 1) + recursiveCompute(n - 2);
	}

	/**
	 * 非递归cache算法:用一个List缓存所有从1~n的Fibonacci值
	 * @param n
	 * @return
	 */
	public static Long cacheCompute(int n) {
		if (n <= 2)
			return 1L;

		List<Long> results = new ArrayList<Long>();
		results.add(1L);
		results.add(1L);

		int length = -1;
		while ((length = results.size()) < n)
			results.add(results.get(length - 2) + results.get(length - 1));
		return results.get(n - 1);
	}

	/**
	 * 非递归swap算法:只用两个变量l1、l2来保存Fibonacci值,不断update和swap
	 * @param n
	 * @return
	 */
	public static Long swapCompute(int n) {
		if (n <= 2)
			return 1L;

		long l1 = 1;
		long l2 = 1;

		int index = 2;
		while (index < n - 1) {
			long l = l2;
			l2 = l1 + l2;
			l1 = l;
			index++;
		}
		return l1 + l2;
	}

	public static void testTime(int n) {
		Long result = 0L;

		long start = System.nanoTime();
		result = recursiveCompute(n);
		long end = System.nanoTime();
		System.out.println("Recursive Compute: " + result + "\tUse Time: " + (end - start));

		start = System.nanoTime();
		result = cacheCompute(n);
		end = System.nanoTime();
		System.out.println("Cache Compute: " + result + "\tUse Time: " + (end - start));

		start = System.nanoTime();
		result = swapCompute(n);
		end = System.nanoTime();
		System.out.println("Swap Compute: " + result + "\tUse Time: " + (end - start));
	}

	public static void main(String[] args) {
		System.out.println("Compute Fibonacci(10):");
		testTime(10);
		System.out.println("\nCompute Fibonacci(20):");
		testTime(20);
		System.out.println("\nCompute Fibonacci(30):");
		testTime(30);
		System.out.println("\nCompute Fibonacci(40):");
		testTime(40);
		System.out.println("\nCompute Fibonacci(50):");
		testTime(50);
	}

}

测试结果:

Compute Fibonacci(10):
Recursive Compute: 55	Use Time: 26944
Cache Compute: 55	Use Time: 52444
Swap Compute: 55	Use Time: 4330

Compute Fibonacci(20):
Recursive Compute: 6765	Use Time: 1528093
Cache Compute: 6765	Use Time: 26463
Swap Compute: 6765	Use Time: 1443

Compute Fibonacci(30):
Recursive Compute: 832040	Use Time: 17896390
Cache Compute: 832040	Use Time: 48595
Swap Compute: 832040	Use Time: 1924

Compute Fibonacci(40):
Recursive Compute: 102334155	Use Time: 2385636507
Cache Compute: 102334155	Use Time: 54850
Swap Compute: 102334155	Use Time: 1924

Compute Fibonacci(50):
Recursive Compute: 12586269025	Use Time: 287928822445
Cache Compute: 12586269025	Use Time: 76501
Swap Compute: 12586269025	Use Time: 2887

去掉递归算法,再测试:

Compute Fibonacci(100):
Cache Compute: 3736710778780434371	Use Time: 274730
Swap Compute: 3736710778780434371	Use Time: 10104

Compute Fibonacci(1000):
Cache Compute: 817770325994397771	Use Time: 1330826
Swap Compute: 817770325994397771	Use Time: 44746

Compute Fibonacci(10000):
Cache Compute: -2872092127636481573	Use Time: 4596307
Swap Compute: -2872092127636481573	Use Time: 326211

Compute Fibonacci(50000):
Cache Compute: -806788626697678875	Use Time: 14161801
Swap Compute: -806788626697678875	Use Time: 1218240
  1. Recursive算法由于不断调用自身,深度计算过多,性能非常低下,当n>=50时,Recursive算法所花的时间已经很难容忍了;
  2. Cache算法和Swap算法只是在while循环里不断计算和更新,其中Cache算法每次将计算值保存在List中,占用的内存过多,性能也没有Swap的好;


© 著作权归作者所有

longrmlife
粉丝 0
博文 2
码字总数 1079
作品 0
东城
私信 提问
"二分查找(Binary Search)"与"斐波那契查找(Fibonacci Search)"

首先,我们来看一个笔者的拙作,一段二分查找代码 //返回值是key的下标,如果A中不存在key则返回-1template <class T>int BinSearch(T* A, const T &key, int lo, int hi){ int mid; while(l...

不高不富不帅的陈政_
2015/09/30
916
0
递归算法转换为非递归算法的技巧

递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调...

fnqtyr45
2017/11/22
0
0
LeetCode算法题-Fibonacci Number(Java实现)

这是悦乐书的第250次更新,第263篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第117题(顺位题号是509)。Fibonacci数字,通常表示为F(n),形成一个称为Fibonacci序列的序...

小川94
02/15
0
0
HTML5 Web Worker的使用

Web Workers 是 HTML5 提供的一个javascript多线程解决方案,我们可以将一些大计算量的代码交由web Worker运行而不冻结用户界面。 一:如何使用Worker Web Worker的基本原理就是在当前javas...

WolfX
2016/02/24
16
0
java递归算法实现

Fibonacci数列:1,1,2,3,5,8,13…… public classFab { public static void main(String args[]){ } private static int fab(int index){ } } 程序分析: 这个实例是非常经典的实例,主......

动听的椰子
2016/03/01
46
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
52分钟前
3
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
3
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部