【算法系列 - 剑指Offer】斐波那契数列 及其 优化方案
AwesomeDevin opened this issue · 0 comments
AwesomeDevin commented
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
JS实现
- 非递归
function Fibonacci(n){
if(n == 0){
return 0
}else if(n==1)
{
return 1
}else{
var arr = []
arr[0] = 0
arr[1] = 1
for(var i = 2;i<=n;i++)
{
arr[i]= arr[i-1] + arr[i-2]
}
return arr[n]
}
}
- 递归
优化前
function Fibonacci(n){
if(n == 0){
return 0
}else if(n==1)
{
return 1
}else{
return generate(n-1)+generate(n-2)
}
}
优化方案1:
尾递归优化,节省内存空间
function Fibonacci(n)
{
// write code here
function get(index,last1=0,last2=1){
if(index <= 0){
return last1
}else if(n==1)
{
return last2
}else{
return get(index-1,last2,last2+last1)
}
}
return get(n)
}
优化方案2:
fib性能不好主要是因为会多次计算重复n,因此需要对n的计算结果进行缓存
const Fibonacci = (() => {
const obj = {}
// obj变量形成闭包,用于缓存fn(n)
return function(n){
if(obj[n]) return obj[n]
if(n===0) return 0
else if(n===1) return 1
else {
res = fn(n-1) + fn(n-2)
obj[n] = res
return res
}
}
})()