10、斐波那契数列

斐波那契数列

• 用JS计算斐波那契数列的第n个值

• 注意时间复杂度

• 0、1、1、2、3、5…

简单分析

• f(0) = 0
• f(1) = 1
• f(n) = f(n - 1) + f(n - 2)

递归-代码演示

function fibonacci(n: number):number {
  if ( n <= 0) return 0
  if ( n === 1) return 1

  return fibonacci(n - 1) + fibonacci(n - 2)
}
1
2
3
4
5
6

缺点

• 递归大量计算
• 时间复杂度是O(2^n) —— 足够系统死机

优化

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

代码演示

function fibonacci(n: number):number {
  if ( n <= 0) return 0
  if ( n === 1) return 1

  let n1 = 1  // 记录n - 1
  let n2 = 0  // 记录n - 2
  let res = 0 // 最终结果

  for (let i = 2; i <= n; i++) {
    res = n1 + n2

    // 记录中间结果
    n2 = n1
    n1 = res
    
  }
  return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

功能测试

fibonacci(0) // 0
fibonacci(1) // 1
fibonacci(2) // 1
fibonacci(8) // 21
1
2
3
4

单元测试

describe('斐波那契数列',() => {
  it('0 AND 1', () => {
    expect(fibonacci(0)).toBe(0)
    expect(fibonacci(1)).toBe(1)
  })

  it('正常情况', () => {
    expect(fibonacci(2)).toBe(1)
    expect(fibonacci(3)).toBe(2)
    expect(fibonacci(8)).toBe(21)
  })

  it('n 小于 0', () => {
    expect(fibonacci(-1)).toBe(0)
  })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

引申——动态规划

• 把一个问题，拆解为多个小问题，逐级向下继续拆解
• 用递归的思路去分析问题，再改为循环来实现
• 算法三大思维：贪心、二分、动态规划

引申问题——青蛙跳台阶

• 一只青蛙，一次可以跳1级，也可以跳2级
• 问：青蛙跳到n级台阶，总共有多少种方式？

动态规划思维分析

• 要跳到1级台阶，就1种方式f(1) = 1
• 要跳到1级台阶，就1种方式f(2) = 2
• 要跳到n级台阶，就1种方式f(n) = f(n - 1) + f(n - 2)