空间复杂度

目录

概念： 

实例1：

实例2：

实例3：递归

实例4：二维数组

实例5：

实例6：斐波那契额数列 

---

 

概念： 

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

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

• 且对于空间复杂度而言，再实践中其实不看重空间复杂度，看重时间复杂度，主要因为我们现在看重的是效率问题 ，所以我们再写代码的时候主要是运用空间来换取时间。
• 不过空间复杂度其实也会溢出的，现在大部分见到代码中，他们的空间复杂度均是再O（1）和O（N）之间。

注意：空间复杂度本质上是计算临时存储空间的变量个数，临时开辟空间的个数，调用函数内部临时开辟的。

且空间复杂度计算的是运行内存的多少。

 大O渐渐表示法：

时间复杂度-CSDN博客https://blog.csdn.net/2301_76445610/article/details/133961910?spm=1001.2014.3001.5501

实例1：

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

实例1中，并未有使用临时变量进行空间的存储和开辟，运用的内存空间是函数中传递调用的，所以这里的空间复杂度是O（1）

实例2：

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

实例2中，使用了临时变量fibArry进行存储了n+1个long long  类型的空间，所以这里的时间复杂度是O（N）

实例3：递归

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

和时间复杂度一样，再递归中空间复杂度是累加的，在这里我们调用递归了N次，而也开辟了N个不同的空间，所以这里的空间复杂度是O（N）

实例4：二维数组

  int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }

根据malloc函数开辟空间以此来建立二维数组，在代码中，我们先开辟了行的空间，一个开辟了N个，而再每一个行的空间内部，又开辟了N个列的空间，于是总共开辟的空间便是N^2

所以这里的空间复杂度是O（N^2） 

实例5：

问：如果一个函数的内部中只定义了一个二维数组a[3][6]，请问这个函数的空间复杂度是多少？

答：函数内部数组的大小是固定的，不论函数运行多少次，所需空间都是固定大小的，因此空间复杂度为O(1)

实例6：斐波那契额数列

实例6：斐波那契额数列 

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

 再时间复杂度我们讲过，时间是累加的，而空间不同，空间不但可以是累加的，也可以进行重复利用，这与栈帧的销毁和重复利用，以及斐波那契额数列的特性有关。

在斐波那契额数列的递归中，它是如上图所示，先完成一条分支，然后再接着完成下一条分支，直到全部完成，而在这里的过程中，它所开辟的空间是会被重复利用的，并不会直接创建一个新的空间， 这也符合了函数栈帧的性质。

因为空间的利用，所以这里的累加的空间，也就仅仅是开辟了N个空间，所以这里的时间复杂度是O（N）

注意，只有空间可以进行利用，而时间只能进行累加！