空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。程序在运行时候动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。而那些静态的空间，比如代码，常量以及简单的变量与空间复杂度无关。
比较下面的程序1和程序2：
程序1：
void reversestr(char *str, int len)
{
for(int i = 0; i < len/2;i++)
{
char tmp;
tmp = str[i];
str[i]
= str[len-i-1];
str[len-i-1] = tmp;
}
}
程序2：
char * reversestr(char *str, int len)
{
char *strnew = (char *) malloc(len+1);
if (strnew == NULL)
{
return NULL;
}
memset(strnew, 0, len+1);
int pos = 0;
for(int
i = len-1; i >=0; i--)
{
strnew[pos++]= str[i];
}
return strnew;
}
程序1和程序2实现的功能都是将一个输入的字符串进行逆置，比如”hello world”逆置为”dlrow olleh”。程序1在计算过程中，只申请了一个临时变量tmp，因此它的空间复杂度为O（1）；程序2则在计算过程中，动态分配了一个内存，而且该内存大小与输入字符串长度成正比，因此该算法的空间复杂度为O（n）。
再看下面这个算法：找出所有数中重复的数，这些数范围都在0与65536之间。
#define MAXMUM 65536
void FindRepeated(int a[], int n)
{
int tmp[MAXMUM];//定义一个局部数组，用来计算数组a[]中重复的数的次数
int i;
for (i = 0; i < MAXMUM; i++)
{
tmp[i] = 0;
}
for (i = 0; i < n; i ++)
{
tmp[a[i]]++;//数组a[]中的元素，在tmp[]中重复一次，加1
}
for (i = 0; i < MAXMUM; i++)
{
if (tmp[i]>1)//如果tmp[i]的值大于1，那么i就是数组a[]中重复的数
printf(“%d”,
i);
}
}
那么，上面的代码的空间复杂度是多少呢？答案是：O(1)。尽管在计算过程中，程序在栈上分配了tmp[MAXMUM]这么大的一个空间，但由于它的大小是常量，不会随着问题的规模扩大而变大，因此空间复杂度就是O（1）。
