定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,反映的是一个趋势,用 S(n) 来定义。

并不是表示空间占用多少。

常见的有O(1),O(n),O(n^2)。

例子

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

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

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

第一行new了一个数组出来,这个数据占用的大小为n。

这段代码的2-6行,虽然有循环,但没有再分配新的空间。

因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)。