JavaScript斐波纳契数列非递归算法
生活随笔
收集整理的這篇文章主要介紹了
JavaScript斐波纳契数列非递归算法
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
一般斐波納契數(shù)列采用遞歸或是數(shù)組緩存的方式，這里的方法不考慮重復(fù)計(jì)算斐波納契數(shù)列的情況。
fibonacci 數(shù)列定義，查看百度百科的解釋>>
n = 1,2 時(shí)，fib(n) = 1
n > 2 時(shí)，fib(n) = fib(n-2) + fib(n-1)
1、遞歸
<script type="text/javascript">
function Fib(n) {
return n < 2 ? n : (Fib(n - 1) + Fib(n - 2));
}
</script>
2、數(shù)組緩存
<script type="text/javascript">
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];
}
}();
</script>
3、直接使用加法
<script type="text/javascript">
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;
}
</script>
對(duì)比：
如果只使用一次運(yùn)算，第三種方法速度最快；
如果多次使用，第二種方法明顯優(yōu)于其它兩種；
在n較大的情況下不推薦使用第一種；n為10*10000的時(shí)候遞歸就已經(jīng)報(bào)內(nèi)存溢出了
下面是在IE8下測(cè)試的結(jié)果(n為100W)：
如果只需要計(jì)算一次，第三種方法應(yīng)該是最優(yōu)的，而且當(dāng)n越大的時(shí)候，數(shù)組占有的內(nèi)存空間也將越大。
完整代碼：
<!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('第一種方法，運(yùn)算時(shí)間：' + test(Fib, num) + '<br/>');
document.write('第二種方法，運(yùn)算時(shí)間：' + test(IterMemoFib, num) + '<br/>');
document.write('第三種方法，運(yùn)算時(shí)間：' + test(fib, num));
document.write('<br/><br/><br/>');
document.write('第二種方法，運(yùn)算時(shí)間：' + test(IterMemoFib, num) + '<br/>');
document.write('第三種方法，運(yùn)算時(shí)間：' + test(fib, num));
</script>
</body>
</html>
轉(zhuǎn)自：http://www.cnblogs.com/meteoric_cry/archive/2010/11/29/1891241.html
總結(jié)
以上是生活随笔為你收集整理的JavaScript斐波纳契数列非递归算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【FCC】Spinal Tap Case
- 下一篇： 【FCC】Sum All Odd Fib