解析空间复杂度_复杂度为 o(n) 的解法是什么意思

概念：空间复杂度是一个数学函数表达式，是对一个算法运行过程中临时占用储存空间大小的量度。

空间复杂度计算的是变量的个数。可以使用大O渐近法。

注意：函数运行时所需要的栈空间（储存参数。局部变量。一些寄存器信息等）

在编译期间就已经确定好了，因此，空间复杂度主要通过函数在运行时显示申请的二外空间来确定。

举个栗子：

int fun(int* arr, int len)
{
	int* tmp = (int*)malloc(sizeof(int) * len);
	//***
	return x;
}

空间复杂度为O（N）

因为malloc空间时，len的大小未知，所以以最坏的情况考虑，就是O（N）

如果len为定制10，那么空间复杂度的为O（1）

一般情况下，会线性变化的就是O（N），常数就是O（1）。

而且空间复杂度一般不是O（N）就是O（1）。

int fun(size_t n)
{
	if (n < 3)
		return 1;
	return fun(n - 1) + fib(n - 2);
}

该递归的时间复杂度是O（2^N），空间复杂度是O（N）

原因：空间是可以多次重复利用的，时间则不会。

空间回收后可以一次重复利用。