1.2.2 空间复杂度

比较常用的空间复杂度有O（1）、O（n）、O（n2）。

（1）常数阶O（1）：如果算法在执行的时候，所需要的临时空间不会变化，即开辟了固定大小的空间，那么这个算法的空间复杂度就是O（1）。比如，前面介绍的二分搜索算法，在搜索的过程中只有一些变量占用了辅助空间，所以二分搜索算法的空间复杂度是O（1）。

（2）线性阶O（n）；如果算法在执行的时候，所需要的临时空间会随着n线性增加，那么这个算法的空间复杂度就是O（n）。最常见的算法例子就是开辟一个有n个数值的数组，具体代码如下所示，求解原来数组中每个元素的平方，该算法的空间复杂度就是O（n）。

（3）平方阶O（n2）：如果把O（n）的代码再嵌套循环一遍，那么它的空间复杂度就是O（n2）了。最常见的算法例子就是开辟一个具有n×n个数值的二维数组，具体代码如下所示，求解该数组中每个元素的平方，该算法的空间复杂度就是O（n2）。

其实我们可以发现，算法的空间复杂度和算法选用的数据结构有密切的关系，如果我们的数据结构就是简单的辅助变量，那么算法的空间复杂度就是O（1）；如果我们的数据结构是一维数组，那么算法的空间复杂度就是O（n）；如果我们的数据结构是二维数组，那么算法的空间复杂度就是O（n2）。