首页 > Python算法 > 认识算法 阅读数:39

空间复杂度的概念与计算

一个算法在计算机存储器上所占用的存储空间,包括算法本身所占用的存储空间,算法的输入、输出数据所占用的存储空间,算法在运行过程中临时占用的存储空间三个方面。

算法本身所占用的存储空间由算法本身的长度决定。在大多数情况下,算法自身占用的空间对算法整体的空间复杂度的影响有限。毕竟一个手写的算法的长度是有限的,而代码用字符串的方式存储,不会占用过多空间。在绝大多数情况下,算法的输入、输出数据所占用的存储空间是由要解决的问题决定的,它不随算法的不同而改变。

算法在运行过程中临时占用的存储空间随算法的不同而异。有的算法只需要占用少量的临时工作单元,而且这些临时工作单元不随问题规模的大小而改变。有的算法需要占用的临时工作单元数量与解决问题的规模 n 有关,它随着 n 的增大而增大,当 n 较大时,将占用较多的存储单元,例如快速排序和归并排序就属于这种情况。

而空间复杂度就是对一个算法所需存储空间的量度,但其并不考虑算法本身所占用的存储空间。若算法的输入、输出数据所占用的存储空间只取决于问题本身,则也不列入考虑范围中。因为后两个因素并不能精准地体现一个算法的优劣。

类似于时间复杂度,空间复杂度也是自变量为输入规模 n 的函数,并考察输入规模趋于无穷时所占用空间的渐近情况,所以空间复杂度也用 O 符号来表示,记作

S (n)=O(f(n))


直接插入排序的时间复杂度是 O(2n),而空间复杂度是 O(1),因为插入排序只是在已存储好的数组或列表上进行排序,不需要额外存储临时变量。一般的递归算法就要有 O(n) 的空间复杂度了,因为每次递归都要存储返回信息,否则大部分递归运算都在做无用功。

时间复杂度和空间复杂度往往是相互制约、相互影响的。在解决同一个问题的时候,当追求降低时间复杂度时,可能会不可避免地提高空间复杂度,即可能导致占用较多的存储空间;反之,当追求降低空间复杂度时,可能会不可避免地提高时间复杂度,即可能导致占用较长的运行时间。所以在设计一个算法的同时,要综合考虑算法的各项性能,从而更有效地提高效率。