空间复杂度：
空间开销（内存开销）与问题规模n之间的关系
例1：
我们依然选择上篇文章中将时间复杂度用到的实例：
void loveyou(int n)//n为问题规模 { int i = 1; while (i <= n) { i++; printf("I LOVE YOU%d", i); } printf("I LOVE YOU More than %d\n", n); }
将该程序放入计算机中，它在内存中，存储形式如下所示：
由此可知，无论问题规模怎么变化，算法运行所需的内存空间都是固定的常量，算法空间复杂度为S(n)=O(1),这也被称为算法原地工作。
算法原地工作是指：算法所需内存空间为常量。
但并不都是无论问题规模怎么变化，算法运行所需的内存空间都是固定的常量的这种情况。
例2：
我们依然选择上篇文章中将时间复杂度用到的实例：
void loveyou(int n) { printf("I LOVE YOU More than %d\n", n); int i = 1; while (i < n) { if (Flag[i] == n) printf("I LOVE YOU%d\n", i); } } //Flag数组乱序存放1-n这些数 int Flag[n]={1.....n}; loveyou(Flag,n);
将该程序放入计算机中，它在内存中，存储形式如下所示：
此时，空间复杂度就和时间规模n有关联，由此可得算法空间复杂度为S（n）=O(4n+8)=O(n)
例3：
void test(int n) { int flag[n][n]; int i; ...... }
对于这个程序代码，我们依然可以根据上面的分析过程进行分析，不过需要提醒的是：
int flag[n][n];//所占内存空间为：4n*n,而不是16n*n //原因：该数组被定义为整形数组，那么该数组一个元素所占据的空间是4B,数组元素的个数有n*n个
由此可得该算法的空间复杂度为：S(n)=4nn+8=O(nn)
例4：
void test(int n) { int flag[n][n]; int other[n]; int i; }
对于这个程序代码，我们分析得出算法空间复杂度为：S(n)=4nn+n+8=O(nn)+O(n)+O(1)=O(n*n).
总结：
程序代码在内存中所占的空间是大小不变的，因此在分析空间复杂度时，只需要分析变量所占的空间，计算出算法空间复杂度后，处理方式依然和时间复杂度相同，保留高阶，忽略低阶（不懂得可以参考上篇文章）
函数递归调用带来的内存开销：
每次调用所需内存空间的大小相同：
举例：
void loveyou(int n) { int a, b, c;//每次调用，a,b,c的值虽然没有改变，但存储位置法会随着n变化 if (n > 1) { loveyou(n - 1); } printf("I love you %d\n", n); } int main() { loveyou(5); }
分析过程如下：
由此，我们可以得出一个结论：空间复杂度=递归调用的深度
void loveyou(int n) { int flag[n]; if (n > 1) { loveyou(n - 1); } printf("I love you %d\n", n); } int main() { loveyou(5); }
与上面那个例子不同的是：该实例中的int flag[n]中的n,也会随着调用次数而变化,因此，每一级数组的长度是不同的，这也导致，每一级的调用空间是不同的。
因此，各级调用的空间复杂程度为:1+2+3+4+5+…+n=[n(1+n)]/2=1/2nn+1/2n,故S(n)=O(n*n).
