算法的空间复杂度（C语言）

1.空间复杂度的定义

算法在临时占用储存空间大小的量度（就是完成这个算法所额外开辟的空间），空间复杂度也使用大O渐进表示法来表示

注： 函数在运行时所需要的栈空间(储存参数，局部变量，一些寄存器信息等)在编译期间就已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

例1：

int* fib(int n)
{
	int* fibarray = (int*)malloc(sizeof(int) * (n));
	if (n == 0)
	{
		return NULL;
	}
	fibarray[0] = 1;
	fibarray[1] = 1;
	for (int i = 2; i < n; i++)
	{
		fibarray[i] = fibarray[i - 1] + fibarray[i - 2];
	}
	return fibarray;

}

怎么查看这段代码的空间复杂度：可以观察到该段代码为了完成这个算法额外申请了n个空间，即空间复杂度：O(n)

例2：

void Bubble_Sort(int a[], int n)
{
	assert(a);
	int exchange = 0;
	for (int end = n; end > 1; --end)
	{
		for (int begin = 1; begin < end; ++begin)
		{
			if (a[begin] < a[begin - 1])
			{
				Swap(&a[begin], &a[begin - 1]);
				exchange = 1;
			}
		}
		if (!exchange)
		{
			break;
		}
	}
}

可以观察到这段代码完成这个算法额外开辟了三个空间 即空间复杂度：O(1)

例3：

int fac(int N)
{
    if(N == 0)
    {
       return 1;
    }
    return fac(N-1)*N;
}

这段递归的空间复杂度为多少了

注：每次递归都是开辟新的空间来进行操作

这段代码从Fac(N) 开始 Fac(N - 1)，Fac(N - 2).....Fac(1)，Fac(0)，所以递归了N次

该算法完成递归额外开辟了N个空间：O(N)

我们来看一段代码

void F1()
{
    int b = 0;
    printf("%p ", &b);
}

void F2()
{
    int a = 0;
    printf("%p ", &a);
}

int main()
{
    F1();
    F2();
    return 0;
}

F1和F2是否使用的同一个空间

运行结果：

可以看到这两个不同函数中的变量居然是用的同一个地址

原因：因为mian函数中是先调用的F1，在F1执行完之后，F1所在的空间被系统收回了，即在执行F2时，F2也是用的这个地址，因此F2和F1所用的空间相同

例4：

long long Fib(int N)
{
	if (N < 3)
	{
		return 1;
	}
	return Fib(N - 1) + Fib(N - 2);
}

这段代码的时间复杂度为：O(2^N)

递归时Fib(N) ——> Fib(N - 1) 和 Fib(N - 2),然后编译器是先将Fib(N - 1)先递归完再进行Fib(N - 2)

递归到最后Fib(2) Fib(1)时先执行的是Fib(2)，随后就是Fib(1)，所以可以推断Fib(1)所用的空间是Fib(2)所释放的空间，所以Fib(1)和Fib(2)所用的空间是一样的所以跟着这个思路往上推，假如N = 5    Fib(5)就额外开辟了4个空间

如图：

一共额外开辟了4个空间

这段代码的时间复杂度;O(2^N)   时间一去不复返，这次不可能执行上一次的操作，不可重复利用

空间复杂度：O(N)    空间用了之后归还，可以重复利用