一般斐波纳契数列采用递归或是数组缓存的方式，这里的方法不考虑重复计算斐波纳契数列的情况。
n = 1,2 时，fibn) = 1
n > 2 时，fibn) = fibn-2) + fibn-1)
1、递归
<script type="text/javascript">
function Fibn) {
return n < 2 ? n : Fibn - 1) + Fibn - 2));
}
</script>
2、数组缓存
<script type="text/javascript">
var IterMemoFib = function) {
var cache = [1, 1];
return functionn) {
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 fibn) {
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>
对比：
如果只使用一次运算，第三种方法速度最快；
如果多次使用，第二种方法明显优于其它两种；
在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 Fibn) {
return n < 2 ? n : Fibn - 1) + Fibn - 2));
}
var IterMemoFib = function) {
var cache = [1, 1];
return functionn) {
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 fibn) {
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 testfn, n) {
var date = +new Date);
fnn);
return new Date).getTime) - date;
}
//document.write'第一种方法，运算时间：' + testFib, num) + '<br/>');
document.write'第二种方法，运算时间：' + testIterMemoFib, num) + '<br/>');
document.write'第三种方法，运算时间：' + testfib, num));
document.write'<br/><br/><br/>');
document.write'第二种方法，运算时间：' + testIterMemoFib, num) + '<br/>');
document.write'第三种方法，运算时间：' + testfib, num));
</script>
</body>
</html>
转自：http://www.cnblogs.com/meteoric_cry/archive/2010/11/29/1891241.html