【九月打卡】第20天 前端面试技能拼图1

课程名称：2周刷完100道前端优质面试真题
课程章节：第3章 前端面试技能拼图1： 数据结构和算法（下），大厂面试必考
主讲老师：双越

课程内容：

今天学习的内容包括：
3-5 求斐波那契数列的第n值-递归算法会导致运行崩溃——使用递归得到第n个值，时间复杂度O(2*n)，导致程序崩溃，不可用。
3-6 -求斐波那契数列的第n值-优化时间复杂度-part1——使用动态规划理念，构建出n个小问题并给出解，得出最终第n值。

课程收获：

求斐波那契数列的第n值

斐波那契数列

• 用JS计算斐波那契数列的第n个值
• 注意时间复杂度
• f(0) = 0
• f(1)= 1
• f(n) = f(n - 1) + f(n - 2)
• 时间复杂度为O(2*n)，非常耗时，不可用

优化

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

动态规划

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

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

今天的 学习了 求斐波那契数列的第n值，使用了两种方法，直接使用递归会导致程序崩溃，算法的时间复杂度为O(2*n)，非常耗时，不可用。使用循环处理则处理非常迅速，非常快，时间复杂度为O(n)。

下一步就是 学习 青蛙跳台阶和移动 0 到数组的末尾了。今天学习就先到这里吧。

坚持打卡，坚持学习，未来可期，加油😀~

​​

​