【数据结构】空间复杂度
目录
一、引入空间复杂度的原因
二、空间复杂度的分析
❥ 2.1 程序运行时内存大小 ~ 程序本身大小
❥ 2.2 程序运行时内存大小 ~ 算法运行时内存大小
❥ 2.3 算法运行时内存大小
❥ 2.4 不考虑算法全部运行空间的原因
三、空间复杂度
❥ 3.1空间复杂度的定义
❥ 3.2 空间复杂度不能准确算出空间大小的原因
❥ 3.3 最关注差空间复杂度的原因
四、空间复杂度的计算
五、常见空间复杂度举例
❥ 5.1 常数阶
❥ 5.2 线性阶
❥ 5.3 平方阶
六、递归与非递归空间复杂度
❥ 6.1 常规函数空间复杂度不重点算栈空间大小的原因
❥ 6.2 递归函数空间复杂度需要算栈空间大小的原因
七、权衡时间与空间效率
一、引入空间复杂度的原因
- 我们知道，一个算法的好坏主要从算法的执行时间和所需要占用的存储空间这两个方面来进行衡量。
- 当一个算法在执行过程中存储数据所需要占用的内存空间的大小，就是空间复杂度。它和时间复杂度一样，是衡量算法性能的重要指标之一。
- 在开发程序之前，分析算法的空间复杂度有助于开发者提前预估程序运行时所需的内存空间，从而合理地规划硬件资源。
二、空间复杂度的分析
❥ 2.1 程序运行时内存大小 ~ 程序本身大小
首先我们先弄清楚什么是程序本身内存的大小，什么是程序运行时内存的大小？有什么关系？
- 程序本身内存的大小：指的是程序文件存储在磁盘等存储设备上所占用的存储空间大小。它主要取决于程序的源代码经过编译、链接等操作后生成的可执行文件所包含的内容，包括代码段、数据段等。
- 程序运行时内存的大小：指的是程序在计算机内存中运行时所占用的存储空间的量。它涉及到程序运行过程中各个方面对内存的使用，包括代码区、数据区（如全局变量、静态变量、常量）、栈区（存储函数调用信息和局部变量）和堆区（用于动态内存分配）等所占用的内存总和。
程序运行时的内存大小是包含程序本身的大小的。
- 通俗来讲，程序本身的大小好比一颗种子，而程序运行的大小就像生长后的植株。
- 程序本身就像一颗种子，其大小是固定的，蕴含着生长的潜力和信息。
- 当种子种下并开始生长后，就如同程序开始运行。当种子长成大树后，会有粗壮的树干和茂密的枝叶，需要占据很大的空间。这就像程序运行时，会在系统中展开庞大的运行架构，占用大量的内存、CPU 等资源，其运行时占据的 “空间” 和要比程序本身所占用的大得多，也有可能会随着业务的发展和数据量的增加不断扩展。
❥ 2.2 程序运行时内存大小 ~ 算法运行时内存大小
程序运行时内存大小和算法运行时内存大小有什么关系？
程序是一个更为宽泛的概念，它由多个部分组成，算法只是程序实现特定功能的核心逻辑。程序运行时，其内存占用除了算法运行所需的内存外，还包括其他诸多方面。算法运行的内存主要用于存储算法执行过程中使用的数据结构、中间变量、递归调用栈等。而程序运行内存还包含程序代码本身占用的空间（代码段）、全局和静态变量占用的空间（数据段）、程序与外部交互的输入输出缓冲区、加载的库文件所占用的内存等。
在一些非常简单的程序中，如果程序的主要功能就是执行一个单一的算法，且没有其他复杂的功能模块、全局变量、输入输出操作等，那么算法运行的内存大小可能与程序运行内存大小非常接近。例如，一个简单的控制台程序，其唯一的功能就是实现一个简单的递归算法计算斐波那契数列，此时程序运行内存主要就是算法运行所需的内存。
但在大多数实际应用中，程序运行时内存的大小通常会大于算法运行时内存的大小。
❥ 2.3 算法运行时内存大小
算法运行时内存大小主要分为以下几个部分：
输入数据空间：存储算法的输入数据
输出数据空间：存储算法的输出数据
暂存数据空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据
暂存数据空间又可以分为：
- 暂存数据：保存算法运行过程中的各种常量、变量、对象等
- 栈帧空间：保存调用函数的上下文数据
- 指令空间：保存编译后的程序指令，但在统计空间复杂度时通常忽略不计
空间复杂度通常统计的是暂存数据和栈帧空间。
❥ 2.4 不考虑算法全部运行空间的原因
- 输入数据空间：
输入数据所占用的空间通常不纳入空间复杂度的考量范围。因为输入数据是算法处理的对象，它的规模是由问题本身决定的，并非算法为完成任务而额外使用的空间。
例：对一个包含n个元素的数组进行排序，数组本身占用的存储空间与算法的空间使用效率并无直接关联，所以不包含在空间复杂度的计算中。
- 程序代码空间：
程序代码本身所占用的存储空间也不影响算法的空间复杂度。代码大小是固定的，不随输入规模的变化而变化，它与算法在处理不同规模输入时的内存需求增长特性没有直接联系。无论输入规模如何，程序代码的空间占用都是恒定的，因此不将其纳入空间复杂度的计算。
- 输出数据空间：
通常而言，输出数据一般不计入空间复杂度。像常规算法的单一返回值，或是排序、查找算法的输出结果，其占用空间固定或由输入决定，不反映额外开销，可不考虑。
但当输出规模与输入紧密相关、或优化目标是输出空间时，则可能计入。
因为空间复杂度更专注于算法本身的逻辑实现对存储空间的需求，即专注于为了完成算法任务，除输入数据本身所占空间之外，算法额外需要的辅助空间大小。所以空间复杂度不考虑算法全部运行空间。
三、空间复杂度
❥ 3.1空间复杂度的定义
空间复杂度（Space Complexity）也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
❥ 3.2 空间复杂度不能准确算出空间大小的原因
- 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，是一种渐近分析，使用大O表示法描述算法在问题规模趋于无穷大时，额外存储空间随问题规模增长的趋势，而不是精确的内存使用量。
- 此外，程序运行时所占用的内存还受到很多与算法本身无关的因素影响，不同的计算机硬件环境（如内存架构、字长等）和软件环境（如操作系统的内存管理机制、编译器的优化程度等）会导致同一算法在不同环境下的实际内存占用有所不同。这会影响程序的实际内存使用，但空间复杂度分析通常不会考虑这些具体环境因素。
❥ 3.3 最关注差空间复杂度的原因
与时间复杂度不同的是，一般情况下，我们只关注最差空间复杂度，因为内存空间是有限的，我们要确保在所有输入数据下都有足够的内存空间。
四、空间复杂度的计算
空间复杂度直接计算变量个数即可，不需要程序占用了多少字节的空间。
计算变量个数的原因：
因为空间复杂度计算规则基本跟时间复杂度类似，也是使用大O渐进表示法来表示空间复杂度。
我们知道，大O渐进表示法表示的是估算值，而不是真实值，主要目的是为了算出空间复杂度属于哪个量级。
举例：
- 一个int型变量，占用空间大小是4bit，4的大小是属于常数阶的，那么它的空间复杂度为O(1)
- n个int型变量的数组，占用的空间大小是4nbit，4n的大小是属于线性阶的，那么它的空间复杂度为O(N)
所以说，为了方便计算空间复杂度的大小，我们可以直接计算变量个数。
五、常见空间复杂度举例
❥ 5.1 常数阶
常数阶的空间复杂度为：O(1)
- 当空间复杂度为O(1)的情况下，也称算法为原地工作或者就地工作。
- 原地工作（就地工作）：指的是算法的执行过程中不使用额外的存储空间，或者使用的额外空间相对输入数据量是常数。即所使用的额外空间量不随问题规模（即输入数据的大小）的变化而变化。
例题1：
//计算BubbleSort的空间复杂度
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;
}
}这段冒泡排序的代码中，分别有end，i，exchange这3个新的变量出现，也就是为这3个变量开辟了空间，因为3是常数，所以冒泡排序的空间复杂度为：O(1)
例题2：
void fun()
{
return 0;
}
void tmp(int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
fun();
}
}注意：在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 𝑂(1)
❥ 5.2 线性阶
线性阶的空间复杂度为：O(N)
例题：
// 计算阶乘递归Factorial的空间复杂度
long long Fac(int N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}Fac递归函数Fac用于计算阶乘。
函数递归调用的深度为N，开辟了N个栈帧，每个栈帧使用了常数个空间。所以空间复杂度为O(N）
❥ 5.3 平方阶
平方阶的空间复杂度为：O(N^2)
例题：
long long Fac(int N)
{
if (N == 0)
return 1;
int arr[N];
return Fac(N - 1) * N;
}在每个递归函数中都初始化了一个数组，总长度为1+2+...+（N-1）+ N = N(N+1) / 2
因为空间复杂度算的是所处的量级，所以是O(N^2)
六、递归与非递归空间复杂度
❥ 6.1 常规函数空间复杂度不重点算栈空间大小的原因
在编译阶段，编译器会根据函数的定义，分析函数中的参数、局部变量以及可能保存的寄存器信息等，从而确定函数调用时一个栈帧所需要的空间大小和布局。
例：
int add(int a, int b)
{
int result;
result = a + b;
return result;
}编译器知道需要为两个int类型的参数a，b，一个int类型的局部变量result，以及返回地址等分配空间。
这是对单个栈帧而言的，是一个固定的模式，不随输入规模或函数执行过程发生显著变化。在大O表示法这种渐进分析中，这部分固定大小的空间被视为常数项。
空间复杂度主要关注的是随着问题规模的增长，算法所需空间的增长趋势。对于常规函数，显式申请的额外空间，如动态分配的数组或对象等，才是随着问题规模可能呈线性、对数等不同趋势增长的部分，是影响空间复杂度的关键因素。
❥ 6.2 递归函数空间复杂度需要算栈空间大小的原因
栈在编译期间确定的是单个栈帧的空间布局，但在递归函数运行时会不断产生新的栈帧。
- 在编译时，无法确定递归函数会被调用多少次，只有在程序运行时，随着递归函数的不断调用和返回，才会实际地在栈上创建和释放栈帧，从而动态地占用和释放栈空间。
- 栈帧数量与递归深度直接相关，而递归深度往往与问题规模有关。
例：在5.2的递归计算阶乘函数，递归深度与输入的n成正比，每一层递归都要占用一定栈空间存储当前层的参数、局部变量等，所以栈空间占用会随着递归深度增加而显著增加。
总言之，递归栈空间中单个栈帧的结构和大小在编译时期是可以确定的，但递归过程中栈空间的实际创建和使用是在运行时动态进行的，并不是完全在编译时期就确定好的。空间复杂度关注的是运行时内存的大小。
七、权衡时间与空间效率
- 实际情况下，算法的时间效率和空间效率同时达到最优非常困难。
- 通常情况下，我们不太关注算法的空间效率，更注重时间效率。
- 但是，像互联网、嵌入式等行业对空间效率也是较为注重的。
- 所以，选择优化时间复杂度或者空间复杂度取决于我们的侧重方面。