数据结构（算法空间复杂度）
造成算法空间复杂度的因素
算法的空间消耗包括三个方面：
Ø实现算法的程序本身需要占据存储空间 Ø实现算法的程序本身需要占据存储空间
Ø待处理的数据需要在内存中存储，占据一定的空间 Ø待处理的数据需要在内存中存储，占据一定的空间
Ø
处理数据的过程中需要一些额外的辅助空间。 Ø 处理数据的过程中需要一些额外的辅助空间。
渐进空间复杂度也称空间复杂度：是当数据规模n趋于无穷时使用辅助空间的量阶，计为S(n)=O(f(n))。
一个数据序列逆置的示例：
实例
int a[10]={1,6,2,5,8,9,5,4,3,12};
int t, i;
for (i=0; i<5; i++)
{ t=a[i];
a[i]=a[10-i-1];
a[10-i-1]=t;
}
为完成n=10个元素的逆置，将a[0]和a[9]交换、a[1]和a[8]交换，最后直到a[4]和a[5]交换。使用的辅助空间为一个变量t，辅助空间数量和元素个数没有关系，故其空间复杂度为O(1)。
int a[10]={1,6,2,5,8,9,5,4,3,12},b[10];
int i;
for (i=0; i<10; i++)
b[i] = a[10-i-1];
for (i=0; i<10; i++)
a[i] = b[i];
使用了具有n个元素空间的数组b作为辅助空间，空间复杂度为O(n)。
对于时间复杂度和空间复杂度的理解
在内存足够大的情况下，算法更加注重时间效率，忽略空间复杂度的计算。或者仅当算法的时间复杂度一致的情况下才可能比较空间复杂度的优劣。
下一篇：
Java面试题记录(含答案)