前言
斐波那契数列定义
斐波那契数列指的是这样一个数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........ 这个数列从第3项开始，每一项都等于前两项之和题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
日常找规律
- 当有1阶时 F(1) = 1
- 当有2阶时 F(2) = 2(可以1阶或者2阶)
- 当有3阶时 F(3) = 3(可以1阶或者1、2阶或者2、1)
- 当有4阶时 F(4) = 5(可以1阶或者1、2、1、1阶或2、1、1、1或2、2、1或2、1、2)
- ...
- 当有n阶时 F(n) = F(n - 1) + F(n - 2)
F(1)=1F(2)=2F(n)=F(n-1)+F(n-2)复制代码
实现方式
当我们得到推导公式，实现函数脑海里面会想到递归实现
递归
- 时间复杂度: O(2^n)
function fiber (n) { if ( n === 1) { return 1 } if ( n === 2) { return 2 } return fiber( n - 1) + fiber( n - 2 )}复制代码 循环
- 时间复杂度: O(n)
- 空间复杂度: O(n)
function fiber (n) { let step = [] step[1] = 1 if ( n >= 2) { step[2] = 2 } if ( n <= 2) { return n } for ( let i = 3; i <= n; i++) { step[i] = step[i - 1] + step[i - 2] } return step[n]}复制代码 循环 + 优化空间复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
function fiber (n) { let prev1 = 1 let prev2 = 2 let result = 0 if ( n <= 2) { return n } for ( let i = 3; i <= n; i++) { result = prev1 + prev2 prev1 = prev2 prev2 = result } return result}复制代码