算法和数据结构之小白（二）

算法

力扣第二题（斐波那契数列）

1. 题目

fib.png

2. 思路

• 递归 重复计算
• 递推 迭代N，将第i个元素设置前两个元素的和

3. 解法

• 递归

var fib = function(N) {
  if(N === 0 || N ===1) {
    return N
  }
  return fib(N - 1) + fib(N - 2)
}

点击提交记录里的通过我们可以看一下我们用了多少时间和空间

递归.png

• 递推

var fib = function(N) {  // N = 2
  let cache = [];
  for(let i = 0;i<=N;i++) {
    if(i === 0 || i ===1) {
     // 当i = 0时 cache[0] = 0
     // 当i = 1时 cache[1] = 1
     // cache = [0,1]
      cache[i] = i
    } else {
      //当 i = 2 时 cache[2] = cache[2 - 1] + cache[2 - 0]
      cache[i] = cache[i - 1] + cache[i - 2]
    }
  }
  // 最后返回cache[2] 也就是 1 + 0 
  return cache[N]
}

点击提交记录里的通过我们可以看一下我们用了多少时间和空间

递推.png

4. 复杂度

• 递归 时间复杂度：O(n²)
• 递推 时间复杂度：O(n) 空间复杂度：O(n)

第二题斐波那契数列完成，大家如果有更好的思路和想法欢迎在下方评论写出，共同学习，共同进步，加油~

happy