当前位置:网站首页>JS for Fibonacci sequence

JS for Fibonacci sequence

2022-06-12 18:02:00 Out of the autistic bird

Fibonacci sequence

The first number is 0, The second term is 1, Each subsequent number is the sum of the first two numbers

//  recursive O(2^n)
function fibonacci(n){
    
  if(n<=0) return 0
  if(n===1) return 1
  return fibonacci(n-1) + fibonacci(n-2)
}

 Please add a picture description

Optimize

  • No recursion 、 Use the cycle
  • Record intermediate results
  • The time complexity is O(n)
// O(n)
function fibonacci(n){
    
  if(n<=0) return 0
  if(n===1) return 1

  let n1 = 1 //  Record n-1 Result 
  let n2 = 0 //  Record n-2 Result 
  let res = 0
  for(let i =2 ;i<=n;i++){
    
    res = n1+n2
    //  Record intermediate results 
    n2 = n1
    n1 = res
  }
  return res
}

Dynamic programming

  • Use recursive thinking to analyze problems , Solve problems with loops
原网站

版权声明
本文为[Out of the autistic bird]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/163/202206121758171399.html