专栏首页游戏杂谈JavaScript斐波纳契数列非递归算法

JavaScript斐波纳契数列非递归算法

一般斐波纳契数列采用递归或是数组缓存的方式,这里的方法不考虑重复计算斐波纳契数列的情况。

fibonacci 数列定义,查看百度百科的解释>>

n = 1,2 时,fib(n) = 1 n > 2 时,fib(n) = fib(n-2) + fib(n-1)

1、递归

function Fib(n) {     return n < 2 ? n : (Fib(n - 1) + Fib(n - 2)); }

2、数组缓存

var IterMemoFib = function() {     var cache = [1, 1];     return function (n) {         if (n >= cache.length) {             for (var i = cache.length; i < n ; i++ ) {                 cache[i] = cache[i - 2] + cache[i - 1];             }         }         return cache[n - 1];     } }();

3、直接使用加法

function fib(n) {     if (n < 2) {         return 1;     }     var a = 1, b = 1;     for (var i = 2; i < n - 1 ;i++ ) {         b = a + b;         a = b - a;     }     return a + b; }

对比:

如果只使用一次运算,第三种方法速度最快;

如果多次使用,第二种方法明显优于其它两种;

在n较大的情况下不推荐使用第一种;n为10*10000的时候递归就已经报内存溢出了

下面是在IE8下测试的结果(n为100W):

如果只需要计算一次,第三种方法应该是最优的,而且当n越大的时候,数组占有的内存空间也将越大。

完整代码:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
 <head>
  <title> new document </title>
  <meta name="generator" content="editplus" />
  <meta name="author" content="" />
  <meta name="keywords" content="" />
  <meta name="description" content="" />
  <meta http-equiv='content-type' content='text/html;charset=utf-8' />
 </head>

 <body>
  
<script type="text/javascript">
	
function Fib(n) {
	return n < 2 ? n : (Fib(n - 1) + Fib(n - 2));
}

var IterMemoFib = function() {
	var cache = [1, 1];
	return function (n) {
		if (n >= cache.length) {
			for (var i = cache.length; i < n ; i++ ) {
				cache[i] = cache[i - 2] + cache[i - 1];
			}
		}
		return cache[n - 1];
	}
}();

function fib(n) {
	if (n < 2) {
		return 1;
	}
	var a = 1, b = 1;
	for (var i = 2; i < n - 1 ;i++ ) {
		b = a + b;
		a = b - a;
	}
	return a + b;
}

var num = 10000*100;

function test(fn, n) {
	var date = +new Date();	
	fn(n);
	return new Date().getTime() - date;
}

//document.write('第一种方法,运算时间:' + test(Fib, num) + '<br/>');
document.write('第二种方法,运算时间:' + test(IterMemoFib, num) + '<br/>');
document.write('第三种方法,运算时间:' + test(fib, num));

document.write('<br/><br/><br/>');

document.write('第二种方法,运算时间:' + test(IterMemoFib, num) + '<br/>');
document.write('第三种方法,运算时间:' + test(fib, num));
</script>

 </body>
</html>

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用hta操作nginx停止、重启

    新上线的webgame需要做一个官网,做好了并上线了(切割、程序、后台,后台使用是java版本的jeecms),但仅仅是自己家的官网做好了,现在上面的想法是需要...

    meteoric
  • JavaScript立即调用的函数表达式

    主要参考知乎上这个问题:javascript 匿名函数有哪几种执行方式 长天之云的回答。

    meteoric
  • 函数声明与函数表达式

    函数声明:直接声明一个函数 function fnName() {};function声明必须有方法名,而出现在表达式里的方法名都会被忽略。

    meteoric
  • webRTC 初探

    webRTC是英文Web Real-Time Communication的缩写,中文翻译网页实时通信,是浏览器不需要服务器的中转,可以直接通信的技术

    frontoldman
  • JavaScript之使用JavaScript模仿oop编程

    wfaceboss
  • 设计模式(5)[JS版]-JavaScript如何实现工厂方法模式?

    在基于类的编程中,工厂方法模式是一种创建模式,该模式使用工厂方法来处理创建对象的问题,而不必指定将要创建的对象的确切类。这是通过调用工厂方法来创建对象的,而不是...

    AlbertYang
  • JavaScript设计模式--观察者模式

    观察者模式(发布-订阅模式):其定义对象间一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都将得到通知。 在JavaScript中,一般使...

    奋飛
  • SeleniumWebDriver如何自动化可视化验证图表和绘图(如折线图,饼图,柱状图)

    前言:图表(Chart)的自动验证是测试自动化的最大挑战之一, 而在我们的应用程序中,我们有大量的图表,接下来将展示我是如何自动化Chart,或许给你一些新的想...

    软测小生
  • Functions在JavaScript中是作为 first class objects存在的

    Functions在JavaScript中是作为 'first class objects' 存在的。这意味着JS中的functions是一种特殊类型的obje...

    lesM10
  • (VUE!jQuery!插件!)盘点前端群的无脑回答0.前言总结

    你是不是在前端群见过很多这种前景:这个怎么做?怎么拿到这些数据?怎么更新整个列表?

    lhyt

扫码关注云+社区

领取腾讯云代金券