第14章-对付空间限制

发表于 | 更新于 | 分类于
本文字数： 3.8k | 阅读时长 ≈ 3 分钟

思考并回答以下问题：

  • 什么是空间复杂度？

本章涵盖：

  • 描述空间复杂度的大O记法
  • 时间和空间之间的权衡

本书至此，在分析各种算法的效率时，我们只关注了它们的时间复杂度。换句话说，就是它们运行得有多快。但有些时候，我们还得以另一种名为空间复杂度的度量方式，去估计它们会消耗多少内存。

当内存有限时，空间复杂度便会成为选择算法的一个重要的参考因素。比如说，在给小内存的小型设备写程序时，或是处理一些会迅速占满大内存的大数据时都会考虑空间复杂度。

既省时又省内存的算法当然是最理想的。但有些情况下我们却只能二者选其一，这时要想做出正确选择，就得仔细分析了。

描述空间复杂度的大O记法

有趣的是，计算机科学家还是用描述时间复杂度的大O记法来描述空间复杂度。

至今我们一直这样用大O记法来描述一个算法的速度：当所处理的数据有N个元素时，该算法所需的步数相对于元素数量是多少。例如，O(N)算法就是处理N个元素需要N步的算法。

O(N2)算法就是处理N个元素需要N2步的算法。

类似地，我们也可以用大O来描述一个算法需要多少空间：当所处理的数据有N个元素时，该算法还需额外消耗多少元素大小的内存空间。让我们看一个简单的例子。

假设要写一个JavaScript函数，它接收一个字符串数组，并返回一个含有那些字符串的大写形式的数组。如果接收的数组是[“amy”, “bob”, “cindy”, “derek”] ，那么返回的就是[“AMY”, “BOB”, “CINDY”, “DEREK”] 。以下是该函数的一种写法。

1
2
3
4
5
6
7
8
9
function makeUpperCase(array) 
{
    var newArray = [];
    for(var i = 0; i < array.length; i++) 
    {
        newArray[i] = array[i].toUpperCase();
    }
    return newArray;
}

makeUpperCase函数接收一个数组作为参数array。然后它创建了一个全新的数组，名为newArray，并将原数组array里的字符串的大写形式填进去。

等到该函数结束的时候，内存里会存在两个数组，一个是array ，它里面是[“amy”, “bob”,”cindy”, “derek”]；另一个是newArray ，它里面是[“AMY”, “BOB”, “CINDY”, “DEREK”] 。

分析该函数的话，你会发现它接收一个N元素的数组，就会产生另一个新的N元素数组。

因此，我们会说这个makeUpperCase函数的空间效率是O(N)。

这种复杂度的图应该很熟悉了。

注意它的画法跟前面章节的O(N)是一样的，只是这次的纵坐标不是代表速度，而是代表内存。

我们再写一个更高效利用内存的makeUpperCase。

1
2
3
4
5
6
7
8
function makeUpperCase(array) 
{
    for(var i = 0; i < array.length; i++) 
    {
        array[i] = array[i].toUpperCase();
    }
    return array;
}

在这第二个版本里，我们没有创建任何新的变量或新的数组，也确实没有消耗额外的内存空间。我们只是变动了原array里的每个字符串，将它们逐一换成大写。最后返回这个修改过的array。

因为该函数并不消耗额外的内存空间，所以我们把它的空间复杂度描述为O(1)。记住，时间复杂度的O(1)意味着一个算法无论处理多少数据，其速度恒定。相似地，空间复杂度的O(1)则意味着一个算法无论处理多少数据，其消耗的内存恒定。

刚才的例子中，无论传入的array包含4个元素还是100个元素，该算法所需的额外的空间都一样（为零）。因此，我们认为新版的makeUpperCase的空间效率是O(1)。

值得一再强调的是，空间复杂度是根据额外需要的内存空间（也叫辅助空间）来算的，也就是说原本的数据不纳入计算。尽管在第二个版本里我们有array这一入参，占用了N个元素的空间，但除此之外它并没有消耗额外的内存，所以它是O(1)。

（有些参考书在计算空间复杂度时是连原始输入也一起算的，那没问题。但此处我们不计算它，当你在其他地方看到某一算法的空间复杂度的描述时，最好留意一下它是否计算原始输入。）

我们比较一下makeUpperCase两个版本的时间复杂度和空间复杂度。

**版 本**
**时间复杂度**
**空间复杂度**
1 O(N) O(N)
2 O(N) O(1)

因为N项数据要花N步去处理，所以两个版本的时间复杂度都是O(N)。然而在空间复杂度方面，第二个版本只有O(1)，与第一个版本的O(N)相比，它对内存的使用效率更高。

因此选择第二个版本更为合理。

时间和空间之间的权衡

第4章我们写了一个用于检查数组是否含有重复值的JavaScript函数。它的第一版是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function hasDuplicateValue(array) 
{
    for(var i = 0; i < array.length; i++) 
    {
        for(var j = 0; j < array.length; j++) 
        {
            if(i !== j && array[i] == array[j]) 
            {
                return true;
            }
        }
    }
    return false;
}

它用了嵌套循环，时间复杂度为O(N2)。

后来我们又写了一版效率更高的，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function hasDuplicateValue(array) 
{
    var existingNumbers = [];
    for(var i = 0; i < array.length; i++) 
    {
        if(existingNumbers[array[i]] === undefined) 
        {
            existingNumbers[array[i]] = 1;
        } 
        else 
        {
            return true;
        }
    }
    return false;
}

该版本会创建一个名为existingNumbers的数组，然后以array遇到的每个数字为索引，到existingNumbers那里找到相应的格子填个 1。如果相应的格子里已被填了1，则可知该数字已经存在，证明有重复值。

因为与第一版的O(N2)相比，它的时间复杂度只有O(N)，所以我们宣称它胜过第一版。确实，单从时间角度考虑的话，第二版是更快的。

但要是把空间也考虑进去的话，你会发现它与第一版相比有一缺点。第一版除了原数组，并不会消耗额外的内存，因此它的空间复杂度为 O(1)。第二版却要创建一个与原数组大小相等的全新数组，因此它的空间复杂度为 O(N)。

①
我们来给两个版本的 hasDuplicateValue 做个全面的对比。

**版 本**
**时间复杂度**
**空间复杂度**
1 O(N2) O(1)
2 O(N) O(N)

可见第一版所用的内存更少，但跑得更慢，第二版虽跑得快但用的内存更多。那要怎么决定该用哪个呢？

答案当然是看情况。如果你想要程序跑得超级快，而且你的内存十分充足，那么用第二版会比较好。但如果你不看重速度，而且你的程序是跑在需要谨慎使用内存的嵌入式系统上，那你应该选择第一版。所有技术讨论都是这样的，当需要做出取舍时，你应从全局看待问题。

写在最后的话

通过这次学习之旅，你已掌握了很多知识，其中最重要的是，你懂得了数据结构和算法的分析，这对代码的速度、内存占用，甚至其可读性都有着重大影响。

在此书中你收获了一套思路清晰的技术分析框架。你明白了计算包含各种细节，尽管大O之类的理论会建议你哪种做法更好，但若考虑其他因素，你可能会做出不同的选择。机器对内存的管理方式和编程语言的底层实现都会影响程序的性能，甚至有时你以为是最高效的做法也可能会随着外部环境的变化而变得低效。

因此，你最好时刻配备性能测试工具来验证你的调优是否有效。测量代码速度和内存消耗的优秀工具有很多。本书的知识只告诉你调优的方向，而测试工具会负责检验你调优的具体实现是否正确。

很多看似复杂、深奥的事物，其实都是由你所掌握的简单概念构筑而成的。不要因为某些资料没解释到位，就以为它很困难而被吓退，你一定能找到更详尽的解释资料。

0%