2-3-算法的空间复杂度分析

一、java中常见内存占用

1.基本数据类型内存占用情况：

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

3.一个引用（机器地址）需要8个字节表示：

例如： Date date = new Date(),则date这个变量需要占用8个字节来表示

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

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

6.java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息

(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

二、算法的空间复杂度

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

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

根据大O推导法则，算法一的空间复杂度为O(1)

算法二的空间复杂度为O(n)

所以从空间占用的角度讲，算法一要优于算法二。

由于java中有内存垃圾回收机制，并且jvm对程序的内存占用也有优化（例如即时编译），我们无法精确的评估一个java程序的内存占用情况，但是了解了java的基本内存占用，使我们可以对java程序的内存占用情况进行估算。由于现在的计算机设备内存一般都比较大，基本上个人计算机都是4G起步，大的可以达到32G

所以内存占用一般情况下并不是我们算法的瓶颈，普通情况下直接说复杂度，默认为算法的时间复杂度。