大家可移步算法分析——大O标记法进行对大O标记法进行了解；

---

目录

一. 理解空间复杂度

二. 空间复杂度 O(1)

三. 空间复杂度 O(n)

---

一. 理解空间复杂度

        既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

        空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用S(n) 来定义，关心算法需要的额外空间。

        在电子计算机时代的早期，时间和空间这两种资源都是极其昂贵的。但是经过几十年不懈的技术革新，计算机的速度和存储容量已经提高了好几个数量级。现在，一个算法所需要的额外空间，往往已经不是我们关注的重点问题了。因此现阶段算法重点关注的是时间复杂度，也就是上一节的内容。

        空间复杂度比较常用的有：O(1)、O(n)，

---

二. 空间复杂度 O(1)

        如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

        代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

---

三. 空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[10];
int j;
for(int i=1; i<=m.length; ++i){
    j = i;
    j++;
}

        这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)