什么是空间复杂度

答案之外多用的格子

假设要从六个数里找出最大的。答案终究只是一个数，可找的过程因解法而异。有的解法在一张便条上记下目前见过的最大值，碰到更大的数就在原处改写，便条从头到尾只有一张。如果每碰到一个更大的数就写进一个新格子，格子就跟着变多；如果为了从大到小重新排列，把所有数整个抄一遍，就要多出和输入一样多的格子。像这样，在得出答案的过程中随手记下的临时格子，就是空间的成本。输入本来就是给定的，不算成本，只数算法在上面另外铺开的格子。

输入（金色）是给定的，不算成本。点“打开临时格子”，就会出现这种解法每碰到更大的数就写进新格子的记录（蓝色）。算作成本的，只有这些额外格子。

量空间成本时把输入除掉、只看额外格子，是为了比得公平。比较拿到同样输入的两种解法，只能数各自多用的格子。那么，只用一张便条的解法总是更好吗？省了地方，会不会在别处吃亏？下面就来看时间和空间之间的交易。

多用地方就快，省地方就慢（交换）

同一个问题，用地方的方式不同，快慢也不同。假设某个值要经常查。一种办法是把答案事先全部算好，写成一张表，每次查只要看一眼表，非常快，但得另外腾出放这张表的地方。另一种办法是不做表，每次查都从头重新算，几乎不占地方，可每次都重复同样的活儿，所以慢。拿地方换时间，或者拿时间换地方，这就叫时间与空间的交换。

交替点“多用地方”和“省地方”。事先备好表的一边（蓝色）占地方多但快，不用表、每次重新数的一边（金色）省地方但慢。问题相同，交易不同。

没有哪一边总是对的，要看情况来选。要经常查，就做表、腾出地方更划算；地方紧，就算慢一点，不用表也更好。那么，省地方具体指什么？在排序这种常见的活儿里，把额外只用 0 格的解法和多用一整份输入的解法放在一起比一比。

原地解决 vs 复制一份

假设要把零散的数从小到大排好。一种办法是在给定的格子里，把两个数的位置互相对调，一点点理顺，一个新格子也不做，只在已有的格子里换位置。这叫原地排序，额外空间是 0。另一种办法是按输入的个数新准备一排空格子，从最小的开始挑，挪进新格子里。结果同样是排好的一列，却多用了一整份和输入一样大的格子。两种解法都能得出正确答案，空间成本却差得很远：一个是 0，一个和输入一样多。

选“原地排序”或“复制一份”，再点“执行排序”。原地（金色）只在同一排格子里换位置，额外是 0 格；复制（蓝色）要新做和输入一样多的格子。结果一样，空间成本不同。

原地，额外 0 格；复制，和输入一样多。答案相同，空间成本却分得清清楚楚。可是“0 格还是和输入一样多”这种说法，是不是有点耳熟？上一课量时间时，我们也分过输入变大活儿却不增加的情况，和活儿随输入一起增加的情况。这副眼镜可以原样戴到空间上。下面就让输入变大，看看额外空间怎么增长。

空间也随输入增长（O(1) 或 O(n)）

上一课的大O，是用一个记号概括输入变大时时间怎么增长。空间也用同样的概括。用一张便条找最大值的解法，不管输入是六个还是一百个，额外格子总是一个。输入再大，额外空间也不变，所以叫 O(1) 空间。复制一份的解法则不同，输入翻一倍，新格子也翻一倍。额外空间和输入成正比地增长，所以是 O(n) 空间。关键在于，用大O这同一件工具，这回量的不是时间，而是空间增长的样子。

点“加大输入”，让 n 变大。O(1)（金色）不管输入多大，额外格子总是一个；O(n)（蓝色）随输入一起增加。这就是把大O原样用在空间上。

同样是大O记号，这回贴在了空间上，而不是时间上。O(1) 表示输入再大，额外空间也限在一个小常数里；O(n) 表示它和输入一起变大。这样，我们就能用两只眼睛看一个算法：要花多少时间，要占多少地方。下面把这两样归成一句话。

总结：看算法的第二只眼睛

归成一句话是这样的。算法在得出答案的过程中，除了答案还会用到临时格子，这些额外格子就是空间成本，输入不算在内。空间和时间常常互相交换：事先做表、多用地方就快，原地解决、省地方就慢。额外空间也随输入增长，总是一格就是 O(1)，和输入一样多就是 O(n)。所以挑好算法时，不能只看快慢。快不快和占多少地方要一起看，才能挑得准。在内存紧张的小设备上，慢一点但省地方的解法，往往才是正确答案。

按顺序点这四步，串成一句话：答案之外多用的格子、空间↔时间的交换、原地 vs 复制、空间也随输入增长（O(1)/O(n)）。空间复杂度就归成了一张图。

现在，我们能用时间和空间两把尺子一起量算法了。在得出同样答案的几种解法里，该在什么情况下选哪一种，我们有了判断的眼光。不光是快慢，连空间成本也一起放上秤，才算真正会挑算法。下一课，我们带着这两把尺子再往前走一步，看看更聪明地解决实际问题的办法。