Zong
学习算法

回想起大学时,学习 C 语言,参加 ACM 竞赛。其实那时候的我对编程就是感兴趣的,当然源于高中学习 Visual Basic 也是一样的,充满了乐趣。这个月我选择学习算法,通过力扣开始我的初学(重回)算法之路。

当初离开算法之路的原因也是因为自认为高等数学没有学好导致的,那么毕业也就没有直接参加开发相关的工作,而是进入银行。

算法,重在解题思路、勤练、融会贯通,那么在我的前端工程师之路上,我也会尽我所能的掌握起来。

算法基本概念介绍

算法(algorithm),在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

时间复杂度

认识大O符号Big O notation

算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模 \(n\) 的函数 \(f(n)\) ,算法的时间复杂度也因此记做

$$T(n) = O(f(n))$$

算法执行时间的增长率与 \(f(n)\) 的增长率正相关,称作渐近时间复杂度,简称时间复杂度。

常见时间复杂度

我整理了一些常见的时间复杂度依次从小到大排序:

$$O(1) < O(log_2n)< O(n) < O(n^2)< O(n^k)$$

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

关于最优解

关于最优解的概念我通过 Google 并没有搜到一个比较合适的答案,但是我理解的最优解就是保证时间复杂度最小的情况下,寻求空间复杂度最小,这才是最优解,并且没有绝对最优解,只有相对最优解。

比较器

算法比较器用于检测你写的算法是否正确,他的优点是比测试用例更接近正确,前提建立在这个比较器是“正确”的。毕竟测试用例的数量是有限的,没有被穷举的。比较器最不容易出错的解法就是暴力解法,最为直接,最为致命。当然你在做算法题的时候,能用暴力解法做出来的题,你的时间复杂度肯定很糟糕,记得避开这一点。

支配理论(英语:master theorem)

在算法分析中,支配理论(英语:master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递回关系式的方法。这种方法最初由Jon Bentlery,Dorothea Haken和James B. Saxe在1980年提出,在那里被描述为解决这种递回的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen,Leiserson,Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。

排序算法

稳定的排序

不稳定的排序

字符串算法

BFPTR算法

这里介绍一个比较好的算法,叫做BFPTR算法,又称为中位数的中位数算法,它的最坏时间复杂度为 \(O(n)\) ,它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。

搜索算法

图算法

数据结构

线性代数

  • 矩阵
    • 思考如何实现转圈打印矩阵
    • 思考如何“之”字形打印矩阵
    • 思考如何在行列都排好序的矩阵中找数

不得不感叹,数学家和科学家的厉害之处,我也加油咯!多刷题。

附:我的力扣主页,以放置在博客底部外链栏。

面试资深前端工程师总结

本着面试也是一种学习的过程,当然进入面试需要精心准备简历,准备简历的时候能把自己看的“相对”比较的透彻,在这2年里自己掌握了什么,经历了什么,用精炼的语句把她们写在我的简历中。而且每次写简历都会发现,对自己以前写的简历不怎么满意,这一次的简历是更上一层楼的版本,我相信这也是一个进步的过程。

那么最后通过面试来真正的认识自己的能力,找到自己想要的方向。千万记住别沉浸在自己公司安逸的环境中,这样找突破点会有些困难,试着跳出这个环境来看看,外面的世界是如何的,越是安逸,越要逼着自己去看看外面。

回顾一下面试的问题:

  • Webpack 热更新是如何实现的?
  • 什么是 CORS ?有多少种方法可以实现?
  • OPTION 请求是如何产生的?
  • 如何自己实现一个 new
  • 什么是原型链?
  • 什么是 EVENT LOOP ?
  • 介绍一下 box-sizing 属性?
  • 什么是 BFC ?
  • 什么是盒模型?
  • 浏览器缓存机制有哪些?
  • 有哪些首屏加载优化策略?
  • 实现按需加载的方式有哪些?
  • 什么是 React Fiber ?
  • 什么是 React Hook ?
  • React Diff 做了哪些优化?
  • ……记不起来了

总之,经过面试,我也找到了自己的欠缺点,自己的弱项。对前端的基础知识点深度抓的还不够深、 CSS 方面基础和广度的欠缺,这是我首要需要解决的问题。当然了,按照我自己的计划继续努力即可,一天比一天强,加油。

React 源码阅读计划

截止 8 月底,从 ReactFiberBeginWork.js 穿插至 ReactDOMComponent.js 回到一些跟 0.3-stable 熟悉的位置。