空间复杂度
算法临时占用存储空间的量度
条目
空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度，记作S(n)=O(f(n))，[1][2]其中，n为问题的规模，f(n)为语句关于n的所占存储空间的函数。[3]常见的空间复杂度有O(1)、O(n)和O(n2)等，当算法运行时占用的临时空间不随某一变量n的改变而改变时，即空间复杂度为常量，表示为O(1)；当算法运行时占用的临时空间随n的改变而改变时，空间复杂度即为O(n)；当算法运行时占用的临时空间随n2的改变而改变时，空间复杂度则为O(n2)，以此类推。[2]
一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面来衡量，即用空间复杂度和时间复杂度来衡量程序的效率。[1]一个算法的空间复杂度是指程序从开始运行到结束所需的存储空间大小，[4]递归算法一般都比较简短，算法本身所占用的存储空间较小，但运行时需要一个附加堆栈，会占用较多的临时存储空间；非递归算法一般较长，因此存储算法本身的空间较大，但运行时需要的存储空间较小。[1]
空 间复杂度是算法运行时所占用空间的一个量度，而不是计算具体的占用空间，[2]一般以数量级的形式给出，如O(1)、O(n)、O(n2)和O(log2n)等。[5]算法的空间复杂度比较容易计算，主要包括局部变量（算法范围内定义的变量）所占用的存储空间和系统为实现递归（如果算法是递归的话）所使用的堆栈空间两个部分。[5]
简介
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。