2.2、空间复杂度

计算机的软硬件都经历一个比较漫长的演变史，作为为运算提供环境的内存，更是如此，从早些时候的512KB、经历了1M、2M、4M等，发展到现在的8G、16G和32G。所以早期算法在运行的过程中对内存的占用情况也是一个经常需要考虑的问题。这里可以用算法的空间复杂度来描述算法对内存的占用。

2.2.1、java长间的内存占用

2.2.1.1、基本数据类型内存占用情况

2.2.1.2、计算机访问内存的方式都是一次一个字节

一个引用需要8个字节

例如：Date date = new Date();这个date的变量这个变量需要8个字节来表示

创建对象

创建一个对象，比如new Date()，除了Date对象内部存储的数据占用的内存，该对象本身也有内存的开销，每个对项的自身开销是16个字节，用来保存对象的头信息。

一般内存使用，如果不够8个字节，都会被自动填充为8个字节

public class A{
    public int a = 1;
}

通过new A()创建一个对象的内存占用如下：

• 整形成员变量a占用4个字节
• 对象本身占用16个字节
  那么创建该对象需要用20个字节，但是由于不是8的倍数，所以会填充到24个字节。

数组对象

java中的数组被限定为对象，一般都会因为记录长度而需要额外的内存，一个原始数组类型的数组一般需要24字节的头信息（16个自己的对象开销，4个保存长度以及4个填充字节）

2.2.2、算法空间复杂度

算法空间复杂度计算公式记作：S(n)=O(f(n))，其中n为输入规模，f(n)语句关于n所占用存储空间的函数。

2.2.3、案例

对指定数组元素进行反转，并返回反转的内容

解法一：

public static int[] reverse(int[] arr){
    int n = arr.length//申请4个字节
    int temp;//申请4个字节
    for(int start = 0,end = n - 1; start <= end; start++;end--){
        temp = arr[start]
        arr[start] = arr[end]
        arr[end] = temp;
    }
    return arr;
}

解法二：

public static int[] reverse(int[] arr){
    int n = arr.length//申请4个字节
    int[] temp = new int[n];//申请n*4个字节+数组自身头信息开销24个字节
    for(int i = n - 1; i >= 0; i--){
        temp[n-1-i] = arr[i];
    }
    return arr;
}

忽略条件判断占用的内存，可以得出内存的占用情况如下：

• 算法一：无论传入的数组大小为多少，始终额外申请4+4=8个字节
• 算法二：4+4n+24=4n+28

根据大O推导法则，算法一的空间复杂度为O(1)，算法二的空间复杂度为O(n)，所以从空间上来讲算法一优于算法二。

由于java中有内存垃圾回收机制，并且jvm对程序的内存占用也有优化，所以无法准确的评估java程序的内存占用情况，但是了解java的基本内存占用，可以使我们对java程序的内存占用情况进行估算。

由于现在计算机设备的内存一般都比较大，所以内存占用一般情况下并不是我们算法的瓶颈，普通情况下所得复杂度都是算法时间复杂度。

但是如果是做嵌入式开发，尤其是一些传感器设备上的内置程序，由于这些设备的内存很小只有nkb，这个时候对空间复杂度就有要求了，但是一般java开发都是服务器的开发，所以问题不大。