第94题 求斐波那契数列的第n值

• 计算斐波那契数列的第n值
• 注意时间复杂度

分析

• f(0) = 0
• f(1) = 1
• f(n) = f(n - 1) + f(n - 2) 结果=前一个数+前两个数 0 1 1 2 3 5 8 13 21 34 ...

斐波那契数列（递归）

• 递归，大量重复计算，时间复杂度O(2^n)，n越大越慢可能崩溃，完全不可用

    /**
     * 斐波那契数列（递归）时间复杂度O(2^n)，n越大越慢可能崩溃
     * @param n:number n
     */
    function fibonacci(n) {
      if (n <= 0) return 0
      if (n === 1) return 1
    
      return fibonacci(n - 1) + fibonacci(n - 2)
    }

    // 功能测试
    console.log(fibonacci(10)) // 55
    // 如果是递归的话n越大 可能会崩溃

拓展-动态规划

• 把一个大问题拆为一个小问题，逐级向下拆解 f(n) = f(n - 1) + f(n - 2)
• 用递归的思路去分析问题，再改为循环来实现
• 算法三大思维：贪心、二分、动态规划

拓展：青蛙跳台阶

• 一只青蛙，一次可跳一级，也可跳两级
• 请问：青蛙一次跳上n级台阶，有多少种方式

用动态归还分析问题

• f(1) = 1 一次跳一级
• f(2) = 2 一次跳二级
• f(n) = f(n - 1) + f(n - 2) 跳n级

斐波那契数列（循环）

• 不用递归，用循环
• 记录中间结果
• 优化后时间复杂度O(n)

    /**
     * 斐波那契数列（循环）
     * @param n:number n
     */
    function fibonacci(n) {
      if (n <= 0) return 0
      if (n === 1) return 1
    
      // ![](https://s.poetries.work/uploads/2023/01/c61bb6c51c6263cf.png)
      let n1 = 1 // 记录 n-1 的结果
      let n2 = 0 // 记录 n-2 的结果
      // n1、n2整体往后移动
      let res = 0 // 记录当前累加结果
    
      // 从2开始才能计算和相加 0 1是固定的
      for (let i = 2; i <= n; i++) {
        res = n1 + n2 // 计算当前结果
    
        // 记录中间结果，下一次循环使用
        n2 = n1 // 更新n2的值为n1的 往后移动累加
        n1 = res // n1是累加的结果
      }
    
      return res
    }

    // 功能测试
    console.log(fibonacci(10)) // 55
    // 不会导致崩溃