背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

对付空间限制

之前在分析各种算法的效率时，我们都只关注它们运行的速度，也就是时间复杂度。但是还有一种衡量复杂度的指标也很有用，那就是算法消耗了多少内存。这个指标就是空间复杂度。

空间复杂度的大O记法

就像描述时间复杂度一样，计算机科学家也用大O记法来描述空间复杂度。

对时间复杂度来说，核心问题就是：如果存在N个数据元素，那么算法需要多少步？

要用大O记法描述空间复杂度，需要修改这个核心问题。对内存消耗来说，核心问题就是：如果存在N个数据元素，那么算法需要消耗多少内存？

假设我们正在编写一个JavaScript函数，该函数会以一个字符串数组为参数，把这些字符串全变成大写，然后用一个数组返回。例如，函数可以读取["tuvi", "leah", "shaya","rami"]数组，然后返回["TUVI", "LEAH", "SHAYA", "RAMI"]。下面是该函数的一种实现。

function makeUppercase(array) {
  let newArray = [];
  for(let i = 0; i < array.length; i++) {
    newArray[i] = array[i].toUpperCase();
  }
  return newArray;
}

在这个makeUppercase()函数中，参数是array。我们会创建一个全新的数组newArray来存储array中的每个字符串的大写版本。

这个函数完成时，计算机内存中就会有两个数组。一个是原来的array，其内容是["tuvi", "leah", "shaya", "rami"]；另一个是newArray，其内容是["TUVI", "LEAH","SHAYA", "RAMI"]。

在分析这个函数的空间复杂度时，可以看出它在包含N个元素的原数组之外，又创建了一个包含N个元素的新数组。

让我们回到核心问题：如果有N个数据元素，那么算法需要消耗多少内存？

因为函数额外生成了N个数据元素（newArray），所以它的空间复杂度是O(N)。

时间和空间的取舍

下面的函数会以一个数组为参数，判断数组中有没有重复值：

function hasDuplicateValue(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length; j++) {
            if(i !== j && array[i] === array[j]) {
                return true;
            }
        }
    }
    return false;
}

这个算法使用了嵌套循环，时间复杂度是O(N2)。我们把这个实现称为版本1。

下面的版本2使用了哈希表，只用了一个循环：

function hasDuplicateValue(array) {
    let existingValues = {};
    for(let i = 0; i < array.length; i++) {
        if(!existingValues[array[i]]) {
            existingValues[array[i]] = true;
        } else {
            return true;
        }
    }
    return false;
}

版本2首先创建了一个空哈希表existingValues。随后我们遍历了数组的每一项。每碰到新项，都把它作为键存入existingValues哈希表。（值可以任意设定，这里用true。）但如果某一项已经是哈希表中的一个键，就返回true，表示找到了重复值。

这两个算法哪一个更高效呢？这要取决于你看重时间还是空间。如果看重时间，那么复杂度是O(N)的版本2比复杂度是O(N2)的版本1高效得多。

但如果你看重空间，那么版本1就比版本2更高效。因为版本2创建了一个哈希表，表中有可能存储传入函数的数组的全部N个值，所以它最多会消耗O(N)空间。而版本1在原数组之外不会消耗任何额外内存，其空间复杂度是O(1)。

下面是该函数的第三个版本，来看一下它和前两个版本比起来效果如何。

function hasDuplicateValue(array) {
    array.sort((a, b) => (a < b) ? -1 : 1);
    for(let i = 0; i < array.length - 1; i++) {
        if (array[i] === array[i + 1]) {
            return true;
        }
    }
    return false;
}

版本3会先对数组进行排序，然后遍历数组中的每一个值，检查它和下一个值是否相等。如果相等，那么就找到了重复值。如果检查到数组末尾，都不存在相等的相邻值，那么数组就没有重复值。

该算法的时间复杂度是O(N log N)。已知最快的排序算法的时间复杂度是O(N log N)，我们可以假定JavaScript的排序算法也是这样。因为排序之外的N步遍历相比之下并不重要，所以整个算法的时间复杂度就是O(N log N)。

结果表明，版本3在时间和空间之间取得了平衡。版本3比版本1运行更快，但比版本2慢。版本3比版本2消耗更少内存，但不如版本1高效。

无论是什么情况，都需要知道对于速度和消耗内存的最低标准。在了解了时间和空间限制之后，就能从众多算法中选出合适的一种，来满足我们对速度和内存消耗的需求。

算法在创建新数组或者新哈希表这种附加数据时需要消耗额外空间。

总结

如果内存有限，那么空间复杂度就成了一个重要因素。如果你有海量数据，或者正在为内存有限的小型设备编程，那么空间复杂度就很重要。

在理想情况下，我们总是会使用又快又省空间的算法。但是有时二者不可兼得，必须做出取舍。每种情况都需要仔细分析，才能知道该优先速度还是优先内存空间。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。