1.3.3　空间复杂性

空间复杂性是对一个算法在运行过程中所占用存储空间大小的度量，一般记为S（n）。注：n是问题规模。

通常，与算法运行时所占用的存储空间相关的因素有：①存储算法本身所占用的存储空间；②算法的输入输出数据所占用的存储空间；③算法在运行过程中所需的辅助变量占用的存储空间，即辅助空间或临时空间。其中，存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随算法的不同而改变。算法在运行过程中所需的辅助空间随算法的不同而异，有的算法只需要占用少量的辅助空间，且该辅助空间不随问题规模的大小而改变，称这种算法是“就地”进行的，是节省存储空间的算法。

可见，一个算法的空间复杂性分析要从多方面综合考虑，要精确地表示它并非易事。在不同的文献资料中，对算法的空间复杂性分析有不同的处理方法，但通常只考虑因素③。在有些算法中，辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况，在设计算法时，应注意空间复杂性的大小。