08 算法评价标准：空间复杂度（大 O 渐进表示法、常见空间复杂度及案例分析、空间换时间）

1 空间复杂度的理解

1.1 基本概念

1.2 大 O 渐进表示法

1.3 空间复杂度的意义

2 常见的空间复杂度

3 空间复杂度案例分析

3.1 常数级空间复杂度 O(1)

3.2 线性空间复杂度 O(n)

3.3 递归函数的空间复杂度

3.4 平方级空间复杂度 O(n^2)

4 空间复杂度与时间复杂度的关系

4.1 时间复杂度 vs 空间复杂度

4.2 以空间换时间

4.3 空间复杂度的重要性

4.4 平衡时间和空间

1 空间复杂度的理解

1.1 基本概念

空间复杂度是评估算法性能的一个重要指标，它描述的是算法在执行过程中所需额外存储空间的大小。这里的 “额外” 是指除了算法本身占用的存储空间（如源代码、常量、简单变量等）以及输入数据占用的存储空间之外的部分。空间复杂度主要取决于算法中数据结构的使用情况，例如数组、链表、栈、队列等。通过分析空间复杂度，可以帮助我们了解算法在不同规模输入下对内存资源的需求，进而优化算法设计，提高程序的执行效率。

1.2 大 O 渐进表示法

大 O 渐进表示法（Big O Notation）是一种数学工具，用于描述算法在输入规模趋向无穷大时，其时间和空间需求的增长趋势。在讨论空间复杂度时，大 O 渐进表示法帮助我们关注算法所需额外存储空间的增长率，而忽略掉那些在输入规模足够大时变得不重要的常数项和低阶项。

假设有一个算法，其所需额外空间 S(n) 是输入规模 n 的函数。如果存在两个正常数 c 和 n0，使得对于所有 n ≥ n0 都有 S(n) ≤ c⋅g(n)，则称 S(n) 是 O(g(n))的，记作 S(n)=O(g(n))。

这里：

S(n) 是算法的实际空间需求。
g(n) 是一个描述 S(n) 增长趋势的函数。
c 和 n0 是常数，用于确保不等式 S(n) ≤ c⋅g(n) 在 n ≥ n0 时成立。

1.3 空间复杂度的意义

资源管理：了解算法的空间复杂度有助于合理分配和管理内存资源，尤其是在资源受限的环境中（如嵌入式系统、移动设备等），这一点尤为重要。

性能优化：通过优化算法的空间复杂度，可以减少内存的使用，从而提高程序的运行效率。例如，减少不必要的数据复制、使用更高效的数据结构等。

可扩展性：对于需要处理大规模数据的应用，低空间复杂度的算法更容易实现良好的可扩展性，能够在数据量增大时保持较高的性能。

成本控制：在云计算等场景下，内存使用量直接影响到服务的成本。优化空间复杂度可以帮助降低运行成本。

2 常见的空间复杂度

常数级空间复杂度 O(1)：

如果一个算法在执行过程中所需的额外空间不随输入规模 n 的变化而变化，则称该算法具有常数级空间复杂度。
例如，一个简单的加法运算 int sum = a + b;，无论 a 和 b 的值如何，它所需的额外空间始终是一个固定大小的整数变量 sum，因此其空间复杂度为 O(1)。

线性空间复杂度 O(n)：

如果一个算法在执行过程中所需的额外空间与输入规模 n 成正比，则称该算法具有线性空间复杂度。
例如，一个算法需要为输入数组中的每个元素创建一个新的副本 int[] copy = new int[n];，则这个新数组的大小与原数组相同，因此其空间复杂度为 O(n)。

对数级空间复杂度 O(log⁡ n)：

如果一个算法在执行过程中所需的额外空间与输入规模 n 的对数成正比，则称该算法具有对数级空间复杂度。
例如，二分查找算法在每次迭代中将搜索范围减半，所需的额外空间主要用于存储中间变量，通常是对数级别的，因此其空间复杂度为 O(log ⁡n)。

平方级空间复杂度 O(n^2)：

如果一个算法在执行过程中所需的额外空间与输入规模 n 的平方成正比，则称该算法具有平方级空间复杂度。
例如，某些矩阵操作可能需要创建一个 n×n 的矩阵，因此其空间复杂度为 O(n^2)。

指数级空间复杂度 O(2^n)：

如果一个算法在执行过程中所需的额外空间与输入规模 n 的指数成正比，则称该算法具有指数级空间复杂度。
例如，某些递归算法或解决组合问题的算法可能需要存储大量的中间结果，导致空间复杂度呈指数增长，因此其空间复杂度为 O(2n)。

常见的空间复杂度关系：

3 空间复杂度案例分析

3.1 常数级空间复杂度 O(1)

如果一个算法在执行过程中所需的额外空间不随输入规模 n 的变化而变化，则称该算法具有常数级空间复杂度 O(1)。这种算法也被称为原地工作算法或就地工作算法。

void test1(int n)
{int i = 1;while (i <= n){i++;printf("%d", i);}
}

在这个示例中，test1 函数的主要逻辑是通过一个 while 循环从 1 到 n 依次输出每个数字。我们来分析一下该函数的空间复杂度：

函数参数 n：作为函数的输入参数，n 占用 4 个字节。
局部变量 i：在函数内部声明的局部变量 i 也占用 4 个字节。

无论输入的 n 值多大，函数在执行过程中始终只需要这两个 int 类型的变量。假设一个 int 类型变量占用 4 个字节，那么整个函数所需的额外空间为：4 (for n) + 4 (for i) = 8 字节，因此，该函数的空间复杂度为 O(1)，即常数级空间复杂度。

3.2 线性空间复杂度 O(n)

如果一个算法在执行过程中所需的额外空间与输入规模 n 成正比，则称该算法具有线性空间复杂度 O(n)。这意味着随着输入规模的增加，算法所需的额外空间也会按比例增加。

void test2(int n)
{int i;int arr[n];
}

在这个示例中，test2 函数的主要逻辑是声明一个大小为 n 的动态数组 arr。我们来分析一下该函数的空间复杂度：

函数参数 n：作为函数的输入参数，n 占用 4 个字节。
局部变量 i：在函数内部声明的局部变量 i 也占用 4 个字节。
动态数组 arr：数组 arr 的大小为 n，每个 int 类型的元素占用 4 个字节，因此数组 arr 占用 4n 个字节。

综上所述，整个函数所需的额外空间为：4 (for n) + 4 (for i) + 4n (for arr) = 4n+8 字节，随着输入规模 n 的增加，额外空间的需求主要由数组 arr 决定，因此该函数的空间复杂度为 O(n)。

3.3 递归函数的空间复杂度

递归函数在执行过程中可能会产生递归调用栈，这会占用额外的内存空间。如果递归调用的深度与输入规模 n 成正比，则称该递归函数具有线性空间复杂度 O(n)。

void Recursion(int n)
{if (n == 1){printf("递归函数");}else if (n > 1){Recursion(n - 1);  // 注意：函数名应一致}
}int main()
{Recursion(5);  // 注意：函数名应一致
}

在这个示例中，Recursion 函数是一个递归函数，其逻辑如下：

基本情况：当 n == 1 时，函数打印 “递归函数” 并返回。
递归情况：当 n > 1 时，函数递归调用自身，传入 n - 1。

每次递归调用都会在调用栈上留下一个帧（frame），直到达到基本情况为止。因此，递归调用的深度与 n 直接相关。具体来说，当 n = 5 时，递归调用的深度为 5 层，如下图所示。

每次递归调用都会在栈上保留一些信息，包括局部变量、参数和返回地址等。假设每次递归调用的栈帧大小为固定值 k，那么对于输入规模 n，总的栈空间为 k×n。因此，该递归函数的空间复杂度为 O(n)。

3.4 平方级空间复杂度 O(n^2)

如果一个算法在执行过程中所需的额外空间与输入规模 n 的平方成正比，则称该算法具有平方级空间复杂度 O(n^2)。这意味着随着输入规模 n 的增加，算法所需的额外空间会以 n^2 的形式增长。

void test4(int n)
{int i, j;int arr[n][n];
}

在这个示例中，test4 函数的主要逻辑是声明一个大小为 n×n 的二维数组 arr。我们来分析一下该函数的空间复杂度：

函数参数 n：作为函数的输入参数，n 占用 4 个字节。
局部变量 i, j：在函数内部声明的局部变量 i 和 j 各自占用 4 个字节。
二维数组 arr：数组 arr 的大小为 n×n，每个 int 类型的元素占用 4 个字节，因此数组 arr 占用 4*n^2 个字节。