空间复杂度：位置也是成本

算法在答案之外多用的格子

假设我们要在六个数里找最大的那个。答案，归根到底就是一个数。可在找的过程中，有的解法只在一张小纸条上记下"目前见过的最大值"，每出现一个更大的数就改写一次。纸条始终是一张。另一种解法，为了从大到小重新排列，把这些数整个又抄写了一遍。这些不是答案本身、而是在做出答案的过程中涂写的临时格子，正是位置的代价。输入反正是给定的，所以不算成本；我们只数算法在它之上多铺开的格子。

输入（金色）只是给定的。点打开临时格子，看算法在答案之外铺开的格子（蓝色）。算作成本的，只有这些额外格子。

衡量位置时，把输入除开、只看额外格子，这是关键。这样才能公平地比较拿到同样输入的两种解法。可是想一想，只用一张纸条就能解的那种，总是更好的吗？省下位置，会不会在别处吃亏呢？下面，我们来看时间和位置之间的那笔交易。

多用位置就快，省位置就慢（交换）

就算是同一个问题，快慢也随你怎么用位置而变。比方说，你得经常去查某个值。一种办法，是事先把答案全算好、写进一张表。每次查只看一眼表就完事，非常快。代价是，得另外腾出位置来放这张表。另一种办法，是不做表，每次查都从头重新算。几乎不占位置，但因为每回都重做同样的活，所以慢。让出位置换时间，或者让出时间省位置。这就叫时间和空间的交换。

点多用些位置和省下位置。事先备表的一边（蓝色）多占位置、快；不用表每次数的一边（金色）省位置、慢。同一个问题，不同的交易。

我们看到，并非哪一边绝对正确，而是按情形来选。要是常查，做表、让出位置就划算；要是位置紧张，哪怕慢一点，不用表也更好。可"省位置"具体是什么意思呢？拿排序这种常见的活儿，把一种一格都不多用的解法，和一种多用整整一份、和输入一样大的解法，并排比一比。

原地求解 对 做一份复制

假设我们把一堆散乱的数从小到大排好。一种办法，是在拿到的格子里，靠互换两个数的位置来整理。一个新格子都不做，只在手里的格子中换位置。这叫原地排序，额外位置是零。另一种办法，是按输入个数新备好一批空格子，每次挑出最小的，搬进那些新格子。结果同样是排好的一列，但多用了整整一份格子、和输入一样多。额外位置花了和输入一样大。两种解法都给出正确答案，可位置的代价，是零还是和输入一样多，差得很远。

选原地排序或做一份复制，再点执行排序。原地（金色）只在同一批格子里换位置，额外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)。所以挑一个好算法，不能只看快慢。多快，和占多少位置，用两只眼睛一起看，才算选得明白。在内存紧张的小设备上，慢一点但省位置的解法，往往才是正确答案。

依次点四个步骤，串成一条线。答案之外多用的格子、位置与时间的交换、原地对复制，以及位置也随输入变多（O(1)/O(n)）。空间复杂度，一张就理清。

如今我们能用时间和位置这两把尺子一起量算法了。在给出同样答案的几种解法里，我们长出了一双眼睛，能判断在什么情形下选哪一个。不只把快慢、连位置的代价也放上秤，才算像个成年人那样去挑算法。下一讲，我们带着这两把尺子，再往前一步，走进更聪明地解决实际问题的那些办法。