常量空间O(1)

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

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

线性空间O(n)

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

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

【例】将一维数组a中的n个数逆序存放到原数组中。

【算法1】交换数组a中每一个位置的值
for(i=0;i<n/2;i++){
    t=a[i];         //创建辅助空间t,变量t与n是多少没有关系.S(n)=O(1)
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}
【算法2】将a中所有元素依次倒着放入b数组
for(i=0;i<n;i++)
    b[i]=a[n-i-1]; //创建辅助数组b，b的大小和数组a的大小一样，S(n)=O(n)
for(i=0;i<n;i++)
    a[i]=b[i];

二维空间O(n*n)

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O()

int[][] matrix=new int[n][n];//O(n^2)
int[][] matrix=new int[m][n];//O(mn)

递归空间

正如下面代码一样，递归代码中没有显示声明变量或者集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。

void fun4(int n){
    if(n<=1){
        return;
    }
    fun4(n-1);
    ...
}

方法调用栈包括入栈和出栈两个操作：

当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中

当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出

还是上述代码，假设现在传入参数5，那么方法fun4(5)的调用信息先入栈：

method fun4

n 5

接下来递归调用相同的方法，方法fun4(4)的调用信息入栈：

method fun4

n 4

method fun4

n 5

以此类推，递归越来越深，栈内的元素也越来越多，最终：

method fun4

n 1

method fun4

n 2

method fun4

n 3

method fun4

n 4

method fun4

n 5

当n=1的时候，触发递归的结束条件，执行return,方法出栈。最终所有入栈的元素都会出栈。

由上面“方法调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n).