05空间复杂度基础教程

定义

空间复杂度是指算法运行过程中临时占用的存储空间大小，反映了程序对内存的需求随输入规模 $n$ 的变化趋势。简单来说，它表示你的程序在运行时会“吃掉”多少内存。
空间复杂度衡量的是算法执行时额外使用的内存空间，而非程序占用的全部内存。
用数学符号表示为：
$$S(n)=O(f(n))$$
表示算法解决规模为 $n$ 的问题时，所需的辅助存储空间最多按 $f(n)$ 的渐进函数增长。
空间复杂度与时间复杂度类似，都用大O表示法表征增长趋势，但关注的是内存资源使用情况，即关心随着输入规模的增大，内存占用是如何变化的。

作用

• 资源限制： 有些设备（如嵌入式系统、手机）内存非常有限，过度占用内存可能导致程序崩溃或运行缓慢。
• 性能： 虽然不如时间复杂度直观，但大量内存的分配和释放也会影响程序的运行效率。
• 优化： 在某些场景下，为了优化时间效率，你可能需要牺牲一些空间；反之亦然。理解空间复杂度有助于你做出权衡。

组成

一个程序在执行时所占用的内存空间可以分为两部分：

固定部分：$O(1)$

• 这部分空间大小与算法的输入规模无关。
• 主要包括：
  • 算法本身的代码（指令集）
  • 常量（const 变量）
  • 简单变量（如 int, char, float 等）
  • 局部变量（不依赖于输入大小的）
• 这部分通常被认为是常数空间，因此在计算空间复杂度时，我们通常忽略它，因为它不随输入规模变化。

可变部分：（依赖于输入规模）

• 这部分空间大小与算法的输入规模（n）有直接关系。
• 主要包括：
  • 动态分配的内存： 例如，根据输入数组大小动态创建的数组、链表节点等。
  • 递归调用栈空间： 递归函数在调用时会把上下文信息压入栈中，递归深度越深，占用的栈空间越大。

在分析空间复杂度时，我们主要关注的是可变部分，因为它决定了算法对内存的实际需求如何随输入规模增长

计算方式

空间复杂度主要统计程序运行时临时开辟的变量、数组、递归调用栈等占用的空间大小。
基本步骤如下：

1. 统计固定空间：如基本变量（int、float等）的空间。通常为常数，记为 $O(1)$。
2. 统计动态空间：输入相关的数据结构，如数组、链表，空间随输入大小变化。
3. 考虑递归调用栈的空间：递归时，调用层数影响空间复杂度。
4. 取峰值空间：算法执行过程中所占用的最大空间。
5. 忽略常数和低阶项，只保留最高阶表示空间复杂度。

常见的空间复杂度计算方式

O(1) - 常数空间复杂度

当算法执行所需的额外空间不随输入规模 n 的变化而变化时，我们称其空间复杂度为 O(1)。

def sum_two_numbers(a, b)