389
前端还要学算法？必须学，而且必须狠狠地学。现在去大厂面试，数据结构与算法已经是标配，要是不会的话，那基本与大厂无缘了。
作为一名前端，虽然在平常开发中很少写算法，但当我们需要深入前端框架、开发语言、开源库时，懂算法将大大提高我们看源码的能力。例如 react 的 diff 算法、webpack 中利用 tree-shaking 优化、v8 中的调用栈、消息队列等，这些就大量使用了算法，看懂了就能更好的了解它们的性能，更高效的解决问题，进阶到更高 Level，赚更多钱。
现在市面上的算法资料很多，但针对前端的算法资料少之又少，所以，这里我整理了一份适用于前端的数据结构与算法系列，希望能帮助你从0到1构建完整的数据结构与算法体系。
本系列预估一共有40多篇，本篇是第一篇。想要更多更快的学习本系列，可以关注公众号「前端瓶子君」和我的「Github（点击查看）」
我们知道，好的数据结构与算法能够大大缩短代码的执行时间与存储空间，那么我们如何去衡量它喃？本节就主要介绍算法性能的衡量指标—复杂度分析。
判断一段代码执行的效率最简单最直观的方式就是把它放在机器上执行一遍，自然就会得到算法的执行时间与占用内存大小。那么为什么还要引入复杂度分析喃？
这主要是因为，通过机器上运行代码来统计算法的性能，有很大的局限性，它容易受测试环境、数据规模影响：
而这些都不是我们想要看到的。我们需要的是不受外在因素影响的、大致的估计算法执行效率的方法。这就是使用复杂度分析的原因。
如何表示算法复杂度，具体来讲就是代码执行的时间、执行消耗的存储空间。例如：
function cal(n) {
let sum = 0; // 1 unit_time
let i = 0; // 1 unit_time
for(; i <= n; i++) { // n unit_time
sum += i; // n unit_time
}
return sum
}
从 CPU 的角度看，每段代码不过是读写数据或操作数据，尽管每次操作 CPU 执行的个数、执行的时间都不同，但我们粗咯把每次执行的时间都一致，称为 unit_time 。
所以上述代码总共执行 (2n+2)*unit_time 时间，即：T(n)=(2n+2)*unit_time ，所以，我们可以写成：
T(n) = O(f(n))
其中：
当 n 很大时，例如 10000，甚至更大，T(n) = O(f(n)) 可以表示为 T(n) = O(n) 。
这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当 n 无限大时，时间复杂度 T(n) 受 n 的最高数量级影响最大，与f(n) 中的常量、低阶、系数关系就不那么大了。所以我们分析代码的时间复杂度时，仅仅关注代码执行次数最多的那段就可以了。
看一个例子：
function fun1(n) {
let sum = 0,
i = 0;
for(; i <= n; i++) {
sum += i;
}
return sum
}
function fun2(n) {
let sum = 0,
sum1 = 0,
i = 0, j = 0;
for(; i <= n; i++) { // 循环1
sum += i;
}
for(i = 0; i <= n; i++) { // 循环2
for(j = 0; j <= n; j++) {
sum += i * j;
}
}
return sum
}
function fun3(n) {
let sum = 0,
i = 0;
for(; i <= n; i++) {
sum += fun(i);
}
return sum
}
fun1 中第1行都是常量，对 n 的影响不大，所以总的时间复杂度要看第2、3行的循环，即时间复杂度为： O(n) 。
fun2 中循环1的时间复杂度为 O(n) ，循环2的时间复杂度为 O(n2)，当 n 趋于无穷大时，总体的时间复杂度要趋于 O(n2) ，即上面代码的时间复杂度是 O(n2)。
fun3 的时间复杂度是 O(n * T(fun)) = O(n*n) ，即 O(n2) 。
所以：T(c+n)=O(n)，T(m+n)=O(max(m, n))，T(n) = T1(n) T2(m) = O(nm)，其中 c 为常量
多项式量级：
let i=1;
while (i <= n) {
i = i * 2;
}
i 都乘以 2 ，直至 i > n ，即执行过程是：20、21、22、…、2k、…、2x、 n2 ，也可以是其他常量 k ，时间复杂度也是： O(log3n) = O(log32 * log2n) = O(log2n)
非多项式量阶：
时间复杂度表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度表示算法的存储空间与数据规模之间的增长关系。例如：
function fun(n) {
let a = [];
for (let i = 0; i < n; i++) {
a.push(i);
}
return a;
}
以上代码我们可以清晰的看出代码执行的空间为 O(1+n) = O(n)，即为 i 及数组 a 占用的储存空间。
所以，空间复杂度分析比时间复杂度分析要简单很多。
时间复杂度受数据本身影响，还分为：
极客时间的数据结构与算法之美
