数据结构 ——— 算法的空间复杂度

目录

前言

空间复杂度的概念

利用例题讲解空间复杂度

例题1：

例题2：

例题3：

结论

前言

在前几章学习了算法的时间复杂度并且练习了时间复杂度的相关代码

数据结构 ——— 算法的时间复杂度-CSDN博客

接下来要学习的是时间的空间复杂度，空间复杂度简单来说就是代码在运行过程中临时占用了多少存储空间大小的量度

空间复杂度的概念

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

且空间复杂度不是计算运行的程序占用了多少字节（byte）的空间，因为计算空间的意义不大，所以空间复杂度算的是变量的个数，空间复杂度计算规则基本跟时间复杂度类似，也是使用大O的渐进表示法

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

利用例题讲解空间复杂度

例题1：

代码演示：

void BubbleSort(int* a, int n)
{
	assert(a);

	// 循环1
	for (size_t end = n; end > 0; end--)
	{
		int flag = 0;

		// 循环2（循环1的内部循环）
		for (size_t i = 1; i < end; i++)
		{
			if (a[i - 1] > a[i])
			{
				// 交换
				Swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
			break;
	}
}

问：计算 BubbleSort 函数的空间复杂度？

代码解析：

整型数组 a 占用了 n 个空间，但是整型数组 a 所占用的空间是提前开辟好的，并不是在 BubbleSort 函数中临时开辟的空间，且 BubbleSort 函数中只临时创建了 flag 变量，也就是临时创建了常数次，由此得出 BubbleSort 函数的空间复杂度函数式：

空间复杂度函数式：F(N) = 1

大O渐进表示法：O(1)

例题2：

代码演示：

long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;

	long long* fibArray = (long long*)malloc(sizeof(long long) * (n + 1));

	fibArray[0] = 0;
	fibArray[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}

	return fibArray;
}

问：计算 Fibonacci 函数的空间复杂度？

代码解析：

代码的意思是：创建一个 fibArray 数组，数组的长度为 n+1，把斐波那契的前 n 项依次存放在 fibArray数组中，最后返回 fibArray

在 Fibonacci 函数中临时开辟了 n+1 个空间，所以得出空间复杂度函数式：

空间复杂度函数式：F(N) = N+1

再根据空间复杂度函数式和大O渐进表示法的规则得出：如果最高阶项存在且不是1，则去除与这个项目相乘的常数（除去 F(N) 中的1 ），得出大O的渐进表示法：

大O渐进表示法：O(N)

例题3：

代码演示：

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

	return Fac(N - 1) * N;
}

问：计算 Fac 函数的空间复杂度？

代码解析：

代码的意思很明显，就是用递归实现 N 的阶乘

这里就涉及到创建栈帧的问题了，第一次进入 Fac(N) 函数，创建一次栈帧，第二次进入 Fac(N-1) 函数，再次创建栈帧，直到 N 为 0 时截至，且每次创建栈帧时只执行了 if 语句，并没有额外开辟空间，所以只计算创建了多少次栈帧，得出空间复杂度函数式和大O的渐进表示法：

空间复杂度函数式：F(N) = N

大O渐进表示法：O(N)

结论

时间是一去不复返的，空间是可以重复利用的