数据结构：空间复杂度_常数空间复杂度

前言

hello，大家好，这篇文章用来介绍空间复杂度的一些相关知识，希望对大家有所帮助，也欢迎大家批评指正。之前博主已经写过一篇介绍复杂度的文章了，主要是对时间复杂度的介绍。大家在阅读本文之前也可以先阅读一下这篇文章数据结构——优雅的复杂度。

1. 空间复杂度是个what？

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

2. 从几个例子来理解空间复杂度的计算

2.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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在这个冒泡排序中，是接受了一个传递过来的数组的。我们在计算这个算法的空间复杂度的时候，是不考虑输入数组的，只考虑算法在运行中额外搞出来的空间。
接下来我们定义了size_t 的end，int change 和size_t i。我们注意，虽然每一次循环进入，i的值会改变，但是i的空间还在那里，没有重新定义。我们要知道，时间是累计的，不可复用，而空间是不累计的，可以复用。
所以，在冒泡排序中变量的个数是3，为常数，则空间复杂度为O（1）。

2.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 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在这个算法中，假设我们要求0~n的的斐波那契数组，我们是需要开出具有n个空间的，空间复杂度为O(N)。虽然这个算法求的不是斐波那契数组，但是在它运行的过程中，是开辟了斐波那契数组的空间的，也就是说，在运行过程中，是开辟出了n个变量空间的，虽然还定义了i等变量，但根据大O的渐进表示法，斐波那契数列的空间复杂度为O(N)。

2.3 阶乘的空间复杂度

long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
1
2
3
4

递归算法的空间复杂度通常是递归的层数。在阶乘中，每一次调用都会建立栈帧，栈帧里面存储参数和局部变量。所以在执行过程中，是建立了n个栈帧的，而每一次调用栈帧的过程中，又会使用常数个空间，根据大O的渐进表示法，空间复杂度为O(N)。

后记

好的，关于空间复杂度我们就先分享到这里了，希望对大家有所帮助。我们下期文章再见，感谢大家多多支持，你们的支持是博主进步的动力。