前端算法之美-入门篇

我不知道自己算不算一个典型的程序员。大家都知道程序员是一个快速迭代（程序员最喜欢用的词之一）的职业，所以需要保持学习，而我也每周都有学，但是只看书，只听专栏，最喜欢看视频学习，因为视频学习几乎不用动脑，所以时间长了，总是逃避写作或者编码实战，这两个东西动不动就要浪费一天或者几天时间，简直是反人类啊，大家是不是也苦恼啊？苦恼也没办法，我这篇文章只会增加你的苦恼，想减少苦恼，看视频去。

言归正传，我上个月写的 设计模式之美-前端 收到了200多个点赞，本来是准备再写一篇对应的算法之美的文章，但是把算法的内容集中在一篇文章里，简直不可读，因此我准备写一个系列。

算法系列

即将上线 前端算法之美-查找算法

即将上线 前端算法之美-进阶篇

数据结构与算法知识总揽

为什么要学算法？

变强，面试。

下面是算法入门的基础概念。

复杂度

算法和数据结构是为了让程序跑的更快更稳定，简言之就是让代码运行更快，存储更省空间。所以我们必须了解自己写的代码的复杂度，即时间复杂度，空间复杂度。

时间复杂度

通俗点说，我们程序运行一个算法需要多长时间。它和执行每一条语句的耗时以及每一条语句的执行频率相关。我们用 “大O表示法” 表示时间复杂度。

下面的代码是求1，2，3...n累加的和。

function cal(n) {
  let sum = 0;
  for (let i = 1; i <= n; ++i) {
    sum += i;
  }
  return sum;
}

从CPU的角度，这段代码的操作是，读数据 -> 运算 -> 写数据，如果每一个操作都是unit_time，第二行和第三行是一个unit_time，而第四行和第五行的for循环是2n个unit_time，加上return操作。时间复杂度就是 2n+3 。分析复杂度的时候为了能更好的展示表达式，我们一般取近似时间，即去掉常数，即复杂度为 n 。所以就可以推断出，所以代码的执行时间T(n)与每行代码的的执行次数成正比。

引出重要概念，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正。

上面一段代码的时间复杂度用大O表示为

空间复杂度

万物都有容量，而应用程序的容器就是内存，内存暂用率越高，程序越容易崩溃。内存的基本单位是字节，一般一个字母或数字占用一个字节（byte），单位间的换算可以参照下面的公式。空间是有限的，如果你一次性读取1000万条数据到内存中，程序可能或崩溃，所以我们编写程序的时候，用必须考虑到空间复杂度，不过它的问题已经得到了一点缓解，现代机器存储已经大大提升了。

1G = 1024M = 1024 * 1024KB = 1024 * 1024 * 1024B

下面的代码，如果我们只考虑最后的数组占用空间，不考虑新建一个数组需要多大内存，它的大小为 11B 左右，数字1-9共占9个字节，数字10占2个字节。

function cal(n) {
  let arr = [];
  for (let i = 1; i <= n; ++i) {
    arr.push(i);
  }
  return arr;
}

cal(10);

复杂度分析

• 单段代码，看高频，循环的次数。
• 多段代码取最大，如果一段代码里单次循环和多重循环，忽略单词，取多重。
• 嵌套代码求乘积，比如递归和多重循环。
• 多个规模求加法，比如方法有两个参数控制两个循环的次数，这时候，就需要取两者复杂度相加。

常用的复杂度级别

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括，O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)。

非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这列算法性能极差。包括，O(2^n)(指数阶)、O(n!)(阶乘阶)。

复杂度分析的四个概念

• 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
• 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
• 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
• 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

一般情况下，我们看一个算法的好坏，是看平均复杂度和最坏复杂度。一个算法在最坏的时间复杂度里也能有很好的性能，也代表了这个算法的可靠程度。

基础算法思想

算法思想一般分为下面几种

算法是程序的核心，而算法思想是算法的核心。一般没有算法基础的，也会枚举算法，比如在一个有序数组中查找其中一项，可以用枚举的思想，直接遍历一次数组，那时间复杂度就是数组的长度 n 。而如果我们用分治算法，后面介绍的 二分查找 就是分治算法，它的时间复杂度会比暴力枚举的算法更低，为 logn。当然我们并不是每次都能找到算法代替，有些场景就只能用枚举算法。

最简单的算法

二分查找基本是每一个面试官面试算法薄弱程序员。给定一个有序的数组对象，要求查找其中一项。这个其实和我们平时玩的一个游戏类似。从1-100中说一个数，然后让别人猜，每次只告诉别人猜大了还是猜小了。你每次都猜中间数，最多只需要7（log2^100）次就能得出答案。

现在有一个数组[1, 3, 4, 6, 8, 9, 10]，求 9 所在 的位置。

function binarySearch(arr, value, lo, hi) {

  if (lo >= hi) {
    return lo;
  }

  const mid = Math.floor((hi + lo) / 2);

  if (arr[mid] > value) {
    return binarySearch(arr, value, lo, mid - 1);
  }
  if (arr[mid] < value) {
    return binarySearch(arr, value, mid + 1, hi);
  }
  if (arr[mid] === value) {
    return mid;
  }

  return -1;
}
const array = [1, 3, 4, 6, 8, 9, 10];
const key = binarySearch(array, 9, 0, array.length - 1);
console.log(key);

现实生活中我们很少用到数据结构和算法，即使用到了，也完全可以通过牺牲性能或者增加代码量来解决这个问题，所以有些人就认为数据结构和算法毫无作用，没有这些我照样能实现功能。学习数据结构和算法不仅仅是可以用更合理的方式实现程序，使应用的程序性能更佳，更重要的是，它会影响你的程序思维，帮助你理解某些框架的底层实现，更方便你造轮子。操作系统、计算机网络、数据算法和数据结构，这些都是你成长避不开的拦路虎，提前拥有这些素养，会让你更加从容面对未来科技的发展。

最后说明，我的算法水平有限，本文的内容参考《算法》一书，以及极客时间专栏《数据结构与算法之美》，b站视频（主讲人是《算法导论》的作者，初学者勿进）。最近也在看《剑指offer》和程序员的数学基础课专栏，这个专栏的作者水平也很高，而且讲解透彻。

https://time.geekbang.org/column/intro/100017301?code=hFy0r14Y4bMhH4L7Zvu5FsarU26sacv%2FTalyLYAB9K4%3D (二维码自动识别)