1.3.1 什么是空间复杂度
在运行一段程序时，我们不仅要执行各种运算指令，同时也会根据需要，存储一些临时的中间数据 ，以便后续指令可以更方便地继续执行。
在什么情况下需要这些中间数据呢？让我们来看看下面的例子。
给出下图所示的n个整数，其中有两个整数是重复的，要求找出这两个重复的整数。
对于这个简单的需求，可以用很多种思路来解决，其中最朴素的方法就是双重循环，具体如下。
遍历整个数列，每遍历到一个新的整数就开始回顾之前遍历过的所有整数，看看这些整数里有没有与之数值相同的。
第1步，遍历整数3，前面没有数字，所以无须回顾比较。
第2步，遍历整数1，回顾前面的数字3，没有发现重复数字。
第3步，遍历整数2，回顾前面的数字3、1，没有发现重复数字。
后续步骤类似，一直遍历到最后的整数2，发现和前面的整数2重复。
双重循环虽然可以得到最终结果，但它显然并不是一个好的算法。
它的时间复杂度是多少呢？
根据上一节所学的方法，我们不难得出结论，这个算法的时间复杂度是O(n 2 ) 。
那么，怎样才能提高算法的效率呢？
在这种情况下，我们就有必要利用一些中间数据 了。
如何利用中间数据呢？
当遍历整个数列时，每遍历一个整数，就把该整数存储起来，就像放到字典中一样。当遍历下一个整数时，不必再慢慢向前回溯比较，而直接去“字典”中查找，看看有没有对应的整数即可。
假如已经遍历了数列的前7个整数，那么字典里存储的信息如下。
“字典”左侧的Key代表整数的值，“字典”右侧的Value代表该整数出现的次数（也可以只记录Key）。
接下来，当遍历到最后一个整数2时，从“字典”中可以轻松找到2曾经出现过，问题也就迎刃而解了。
由于读写“字典”本身的时间复杂度是O(1) ，所以整个算法的时间复杂度是O(n) ，和最初的双重循环相比，运行效率大大提高了。
而这个所谓的“字典”，是一种特殊的数据结构，叫作散列表 。这个数据结构需要开辟一定的内存空间来存储有用的数据信息。
但是，内存空间是有限的，在时间复杂度相同的情况下，算法占用的内存空间自然是越小越好。如何描述一个算法占用的内存空间的大小呢？这就用到了算法的另一个重要指标——空间复杂度（space complexity） 。
和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。
程序占用空间大小的计算公式记作S(n)=O(f(n)) ，其中n为问题的规模，f(n)为算法所占存储空间的函数。
1.3.2 空间复杂度的计算
基本的概念已经明白了，那么，我们如何来计算空间复杂度呢？
具体情况要具体分析。和时间复杂度类似，空间复杂度也有几种不同的增长趋势。
常见的空间复杂度有下面几种情形。
1. 常量空间
当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1) 。例如下面这段程序：
1. void fun1(int n){
2. int var = 3;
3. …
4. }
2. 线性空间
当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模n成正比时，空间复杂度记作O(n) 。
例如下面这段程序：
1. void fun2(int n){
2. int[] array = new int[n];
3. …
4. }
3. 二维空间
当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O(n 2 ) 。
例如下面这段程序：
1. void fun3(int n){
2. int[][] matrix = new int[n][n];
3. …
4. }
4. 递归空间
递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。
“方法调用栈”包括进栈 和出栈 两个行为。
当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。
当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。
下面这段程序是一个标准的递归程序：
1. void fun4(int n){
2. if(n<=1){
3. return;
4. }
5. fun4(n-1);
6. …
7. }
假如初始传入参数值n=5，那么方法fun4（参数n=5）的调用信息先入栈。
接下来递归调用相同的方法，方法fun4（参数n=4）的调用信息入栈。
以此类推，递归越来越深，入栈的元素就越来越多。
当n=1时，达到递归结束条件，执行return指令，方法出栈。
最终，“方法调用栈”的全部元素会一一出栈。
由上面“方法调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n) 。
1.3.3 时间与空间的取舍
人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。
就如一个大财主，基本不必为日常花销伤脑筋；而一个没多少积蓄的普通人，则不得不为日常花销精打细算。
对于计算机系统来说也是如此。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的利用方式。
但是，正所谓鱼和熊掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。
在1.3.1小节寻找重复整数的例子中，双重循环的时间复杂度是O(n 2 )，空间复杂度是O(1)，这属于牺牲时间来换取空间 的情况。
相反，字典法的空间复杂度是O(n)，时间复杂度是O(n)，这属于牺牲空间来换取时间 的情况。
在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。
此外，说起空间复杂度就离不开数据结构。在本章中，我们提及散列表、数组、二维数组这些常用的集合。如果大家对这些数据结构不是很了解，可以仔细看看本书第2章关于基本数据结构 的内容，里面有详细的介绍。
关于空间复杂度的知识，我们就介绍到这里。时间复杂度和空间复杂度都是学好算法的重要前提，一定要牢牢掌握哦！