浅识数据结构之空间复杂度

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

文章目录

一. 前言
二. 空间复杂度
- 2.1 概念
- 2.2 常见的空间复杂度
- 2.3 不常见的空间复杂度，并无实际应用意义。
三. 结语

一. 前言

了解空间复杂度相对于了解时间复杂度来说较为容易一些。
因为时间复杂度需要对程序内部或函数内部的基本语句执行次数进行判断，又时会牵扯到递归，迭代，循环等多重因素，所以计算起来相对复杂。
而空间复杂度只是代表着对一个算法在运行过程中临时占用的储存空间大小的一个量度，并且这个临时的占用大多是指除了主体函数原有的变量之外，再实现算法时额外创建的变量，或是指在递归等函数调用情况下的函数调用次数。
下面进入正式内容。

二. 空间复杂度

2.1 概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
大O渐进表示法：取影响量最大的项作为O( )的内容，且系数可以忽略。

2.2 常见的空间复杂度

O( 1 ) ：常数值的空间复杂度，一般是指调用函数次数或额外创建变量次数可以通过计数的方式的到确切的值。
O( N )：一般指递归次数为 N 或创建额外变量次数为 N 时的情形。
O( N² ) ：这种情形相对来说较为少见，但还是作为举例列明，常见的状况有创建了一个额外的二维数组，他们的额外占用空间为未知量一维数组的个数 N × 未知量一维数组中的个数 M，故空间复杂度为 N²，因 N 趋近于无穷时 N 与 M 的差值可以忽略不计，直接记为 N²。

2.3 不常见的空间复杂度，并无实际应用意义。

下面见一个经典的斐波那契数问题：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

当我们调用这个函数时，若所求值为第64个斐波那契数时还较为容易计算，不难看出在计算结果时，我们的函数调用了2 ^ ( 64 - 2 ) 次，故我们可以将此函数调用的空间复杂度记为O ( 2^N ) 当我们计算的数值序次偏大时，可能会消耗更多的时间，故这样的函数在实际生活中也并没有很大的应用意义。

但我们可以对其进行优化，将O ( 2^N ) 转化为 O( N )。

// 时间复杂度：O(N)
unsigned long long Fib(size_t N)
{unsigned long long f1 = 1;unsigned long long f2 = 1;unsigned long long f3 = 0;for (size_t i = 3; i <= N; i++){f3 = f1 + f2;f1 = f2;f2 = f3;}return f3;
}