算法的空间复杂度

我会带着你远行 2022-09-17 02:00 127阅读 0赞

我们知道衡量算法好坏的两个因素分别是时间复杂度和空间复杂度。上一节我们说了时间复杂度，现在我们来看看空间复杂度。

那么，什么是空间复杂度呢？我们知道，时间复杂度是执行算法的时间成本，那么，笼统来讲，空间复杂度就是算法执行的空间成本。在运行一段程序时，我们不仅要执行各种运算指令，同时也会根据需要，存储一些临时的中间数据，以便后续指令可以更方便地继续执行。那么存储这些中间数据所需要地成本也属于算法的空间复杂度。那么什么时候需要存储一些中间数据呢？举例来说：有一个需求，需要从给定的一列数中找出重复的数字。那么针对这个需求，最朴素的方法就是双重循环，即遍历整个数列，每遍历到一个新的整数就开始回溯之前遍历过的所有整数，看看遍历过的这些整数里有没有与待遍历的数值相同的。假如给定的数列是：3、1、2、5、4、9、7、2。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_20_color_FFFFFF_t_70_g_se_x_16][]

以上需求使用双重循环当然可以得到最终结果，但是其时间复杂度为![O(n^\{2\})][O_n_2]。对我们来说，这个时间复杂度还是有些高的，我们需要改变算法来提高效率，最简单的方法就是使用中间数据来提高效率。 那么如何利用中间数据呢？还是以上述数列为例，当遍历整个数列时，每遍历一个整数，就把该整数存储起来，就像放到字典中一样。当遍历下一个整数时，不必再去回溯向前比较，而是直接去字典中查找，看看有没有对应的整数即可。那么遍历上述数列之后得到的一个字典结构的数据为：

![992e54c68eeb4e45ac0a6e88203b09bf.jpg][]

该字典结构的数据左边的 key 代表整数的值，右边的 value 代表整数出现的次数。当遍历到最后一个整数 2 时，发现 2 在字典中已经出现过，那么就证明该数列中重复的数字是 2。

由于读写字典本身的时间复杂度是![O(1)][O_1]，所以整个算法的时间复杂度是![O(n)][O_n]，和最初的双重循环的方法相比，效率大幅度提高了。上述提到的字典结构的数据，其实是一种特殊的数据结构，叫“散列表”。这个数据结构需要开辟一定的内存空间来存储有用的数据信息。但是内存空间是有限的，在时间复杂度相同的情况下，算法占用的空间自然是越小越好，即空间复杂度越小越好。和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用大 O 表示法。程序占用空间大小的计算公式为![S(n) = O(f(n))][S_n_ _ O_f_n]，其中 n 为问题的规模，f(n) 为算法所占用存储空间的函数。

那么空间复杂度该如何计算呢？和时间复杂度类似，空间复杂度也有几种不同的增长趋势。常见的空间复杂度有下面几种情形。

场景一：常量空间。当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作![O(1)][O_1]。

场景二：线性空间。当算法分配的空间是一个线性的集合时，比如数组，并且集合大小和输入规模 n 成正比时，空间复杂度记作![O(n)][O_n]。

场景三：二维空间。当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作![O(n^\{2\})][O_n_2]。

场景四：递归空间。递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。“方法调用栈”包括入栈和出栈两个动作。当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。当方法返回时，执行出栈操作，把调用的方法和信息从栈中弹出。如有一个递归程序：

void fun(int n) {
        if (n <= 1) {
            return;
        }
        fun(n - 1);
        // do something
    }

假如初始传入参数值为 5，那么方法 fun(5) 的调用信息先入栈

![d444821d983b46828acc500076868902.jpg][]

接下来递归调用相同的方法，方法 fun(4) 的调用信息入栈

![c9549f5e2be046ed95cdf7ade37522d7.jpg][]

以此类推，递归越来越深，入栈的元素就越来越多

![cfa8945edfac448ab08856991ceaaf0a.jpg][]

最终，“方法调用栈”的全部元素会一一出栈。

由上述出入栈的过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是 n，那么空间复杂度就是![O(n)][O_n]。

人们之所以花时间去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。就好像一个大财主基本上不必为日常开销伤脑筋；而一个没有多少积蓄的穷人，就不得不为日常花销精打细算。对于计算机系统来说也是如此。虽然目前计算机的 CPU 处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的利用方式。但是正如鱼和熊掌不可兼得一样，很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。平时基本上都是采用牺牲空间复杂度来换取时间复杂度。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54Sm5pyo55m9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/87029504d3534859b960c056614d1467.png
[O_n_2]: https://latex.codecogs.com/gif.latex?O%28n%5E%7B2%7D%29
[992e54c68eeb4e45ac0a6e88203b09bf.jpg]: /images/20220828/05e88f9c54404bf6b59dc4a8a5edf8d6.png
[O_1]: https://latex.codecogs.com/gif.latex?O%281%29
[O_n]: https://latex.codecogs.com/gif.latex?O%28n%29
[S_n_ _ O_f_n]: https://latex.codecogs.com/gif.latex?S%28n%29%20%3D%20O%28f%28n%29%29
[d444821d983b46828acc500076868902.jpg]: /images/20220828/13d3c61b0c4645308c02f1f1dfde36db.png
[c9549f5e2be046ed95cdf7ade37522d7.jpg]: /images/20220828/6f246f68309c427bb96a5a1c6a77c5be.png
[cfa8945edfac448ab08856991ceaaf0a.jpg]: /images/20220828/9e185234ff814707b5438e659e038f4e.png