<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
let fbnqSave = {};
function fbnq (i,x) {
// body...
function inner(x){
if(x<=0){
console.log('输入错误！')
return;
}
if(x===1||x===2){
return 1;
}else{
if(fbnqSave[x]){
return fbnqSave[x];
}
return inner(x-1)+inner(x-2);
}
}
var res = inner(x);
if(i === x){
console.time('log')
}
fbnqSave[x] = res;
}
function fbnqsl(i){
console.timeEnd('log')
for(var k = 1; k <= i; k++){
fbnq(i,k);
}
}
</script>
</body>
</html>
用递归的方法计算斐波那契数列，一旦输入的数值太大，那么递归算法时间就会非常长，导致超过60之后几乎无法计算。时间复杂度呈指数增长。
但可以利用缓存来优化计算，上述代码可以极大的提高计算效率。计算入口在fbnasl()函数上。
PS：利用迭代也很简单，此题旨在研究缓存的重要性
网友评论