「时间管理」JavaScript算法时间、空间复杂度分析

本文已收录在Github github.com/Geekhyt，感谢Star。

经过数据结构与算法先导篇的洗脑，不知道大家对数据结构与算法重要性的认知有没有上了一层台阶。(虽然阅读量少的可怜)。没看过的建议先去看先导篇前端如何搞定数据结构与算法(先导篇)

不过没关系，至少是有同学在评论区反馈期待下一篇的，那就要坚持把这个系列写下去，今天来给大家聊一聊在数据结构与算法中占了半壁江山的概念。

时间复杂度和空间复杂度

鉴别一名工程师是否是算法高手的方法之一就是考察他对复杂度分析的掌握程度。说起来可能有点玄幻，算法高手对复杂度分析一般讲究的都是感觉。

「时间管理大师 艾克：有的时候，时光还是有他的好处的。两极反转！」

• 拿英雄联盟举例，比如当 IG 夺得 S 系列赛总冠军后，你会发现一大群只有意识，但操作已经跟不上的玩家出现在排位赛的视野当中。(没错，就是我们)在学生时代，我们也是钻石、大师级的高手。然而因为工作，我们只能告别我们的青春。但是，意识还在！

回到本文，面试时面试官考察你算法能力的时候，时间复杂度和空间复杂度也是绕不过去的坎。你不仅需要掌握多种解题思路，而且要能够从复杂度分析的角度找到最优解，这样才能征服面试官。工程中，选取最优的算法则更为重要。一个优秀的算法能节约的系统成本和维护成本都是巨大的。

「话不多说，上才艺！」

(上概念)

首先理解时间和空间：

• 「时间：执行当前算法所消耗的时间」
• 「空间：执行当前算法需要占用多少内存空间」

再加上复杂度：

• 「时间复杂度：全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。」
• 「空间复杂度：全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。」

也就是说，算法的执行效率由执行时间、存储空间两个方面决定。复杂度分析就是用来分析算法执行效率与数据规模之间的关系，包括时间复杂度和空间复杂度。

为什么搞出这两个概念呢？还嫌我需要理解的概念不够多吗？

其实，你也可以进行事后统计法，俗称 「马后炮」。不过既然都叫马后炮了，那肯定是有它的缺点的。

• 事后统计的测试一般都需要依附于具体的环境，比如公司的 DEV、SIT、UAT 等环境机器的配置都不同，那么测出来的结果也会有差别。说白了，你拿同样一段代码，在不同的处理器下 (i9、i5、i3) 来运行，测试出来的结果也是不同的。
• 除了环境，测试结果受数据规模的影响也很大。熟悉排序算法的同学们肯定知道，不同的数据规模下，排序算法的执行效率也会不同。

所以，我们需要一种复杂度分析法，进行事前分析。帮助我们在写代码的过程中尽可能的降低复杂度，这样代码不但在不同的环境下都能以最快的效率执行。而且，这种方法也不需要用具体数据规模的数据来进行测试，就可以粗略的计算出执行效率。这样就把事后统计法的缺点给 cover 了，一举多得。

大 O 表示法

大 O 符号由德国数论学家保罗·巴赫曼 Paul Bachmann 在 1892 年的著作 《解析数论》首先引入，后由另一位德国数论学家 艾德蒙·朗道 Edmund Landau 推广。

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

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

• T(n)：代码执行的时间
• n：数据规模
• f(n)：每行代码执行的次数总和
• O：表示 T(n) 与 f(n) 成正比

注意，初学者可能会认为这种方法就代表真实的代码执行时间，并不是这样，其代表的是代码的执行时间随数据规模增长的变化趋势。

常见的时间复杂度

按数量级递增如下：

• 常量阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlogn)
• 平方阶 O(n^2)
• 立方阶 O(n^3)
• 指数阶 O(2^n)
• 阶乘阶 O(n!)

其中，指数阶和阶乘阶会随着数据规模 n 的增大，执行时间急剧增长，十分低效，我们暂且不去分析。下面我们通过代码来逐一理解其余的时间复杂度。

常量阶 O(1)

const a = 1;
let b = 2;

上述代码，执行时消耗的时间不受某个变量 (n) 的增长而影响，所以它的时间复杂度为 O(1)。也就是说，一般情况下除了循环语句、递归语句，时间复杂度都为 O(1)。

对数阶 O(logn)

let i = 1;
const n = 6;
while (i < n) {
  i = i * 2;
}

观察上述代码，当循环 x 次后，循环退出。也就是说 2 的 x 次方等于 n。那么 x = log2^n，也就是循环 log2^n 次后循环退出，得出时间复杂度为 O(logn)。二分查找的时间复杂度就是 O(logn)。

线性阶 O(n)

const n = 996;
for (let i = 0; i <= n; i++) {
    console.log('来过' + i +'次前端食堂吃饭');
}

毫无疑问，for循环里的代码会执行 n 遍，所以这类代码的时间复杂度就是 O(n)。计数排序、基数排序、桶排序的时间复杂度都是 O(n)。

线性对数阶 O(nlogn)

let j = 1;
const n = 6;
for (let i = 0; i <= n; i++) {
    while (j < i) {
        j = j * 2;
    }
}

理解了对数阶和线性阶，线性对数阶理解起来就很容易了，就是将时间复杂度为 O(logn) 的代码循环 n 遍，那么它的时间复杂度就是 O (nlogn)。归并排序、快速排序、堆排序的时间复杂度都是 O(nlogn)。

平方阶 O(n^2)

const n = 6;
for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= n; j++) {
        console.log('前端食堂的饭真香');
    }
}

平方阶就是把 O(n) 的代码再嵌套一层循环，它的时间复杂度就是 O(n^2)了。冒泡排序、插入排序、选择排序的时间复杂度都是 O(n^2)。

至于 O(n^3) 就是在 O(n^2) 的基础上再嵌套一层循环。(俄罗斯套娃)

我们采用大 O 表示法进行复杂度分析的时候，是可以忽略系数的，一般情况下只需要关注循环执行次数最多的一段代码进行分析即可。

除此之外，「还有最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度以及均摊时间复杂度等」。在实际中，大多数情况下并不是特别常用，这里不再展开。

在现实中，往往代码会比较复杂，这里总结了几条判断时间复杂度的小技巧送给你：

• 单段代码看高频：循环
• 多段代码取最大：有循环和多重循环的情况，取多重循环的复杂度
• 嵌套代码求乘积：循环中的递归
• 多个规模求和：分别有两个参数控制两个循环的次数，取二者的复杂度相加

常见的空间复杂度

• O(1)
• O(n)
• O(n^2)

我们还是通过代码来逐个分析：

O(1)

const a = 1;
let b = 2;

我们定义的变量a、b所占有的空间并不会随着某个变量的变化而变化，所以它的空间复杂度为 O(1)。

O(n)

let arr = [];
const n = 996;
for (let i = 0; i < n; i++) {
    arr[i] = i;
}

arr 所占用的内存由 n 来决定，会随着 n 的增大而增大，所以它的空间复杂度就是 O(n)。「如果初始化一个二维数组 n*n，那么它的空间复杂度就是 O(n^2)。」

除此之外，O(logn)、O(nlogn) 这样的对数阶空间复杂度在平时也很少见，这里不再展开。

「一般在实际中，空间复杂度和你初始化的数组长度有关。除此之外，也和递归的深度有关。」

时空转换

时间复杂度和空间复杂度往往是相互影响的，两者不可得兼。在算法解题套路以及工程中中，根据实际情况，常用的做法就是空间换时间。比如：记忆化搜索、缓存等。