一、空间复杂度介绍

• 程序的空间复杂性（space complexity）是指运行完一个程序所需要的内存大小

对一个程序的空间复杂性感兴趣的主要原因如下：

• ①如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序所需的内存大小
• ②对任何一个计算机系统，都想要知道是否有足够可用的内存来运行该程序
• ③一个问题可能有若干个内存需求各不相同的解决方案。比如，对于你的计算机来说，某 个C + +编译器仅需要1 M B的空间，而另一个C + +编译器可能需要4 M B的空间。如果你的计算机 中内存少于4 M B，你只能选择1 M B的编译器。如果较小编译器的性能比得上较大的编译器，即 使用户的计算机中有额外的内存，也宁愿使用较小的编译器
• ④可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。例如，有一个电路模 拟程序，用它模拟一个有 c个元件、w个连线的电路需要 2 8 0 K + 1 0 *（c+w）字节的内存。如果 可利用的内存总量为6 4 0 K字节，那么最大可以模拟c+w≤3 6 K的电路

空间复杂度的组成

• ①指令空间（instruction space）：指令空间是指用来存储经过编译之后的程序指令所需的空间
• ②数据空间（data space）：数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成：
  • 常量和简单变量 所需要的空间
  • 动态数组和动态类实例等动态对象所需要的空间
• ③环境栈空间（environment stack space）：环境栈用来保存暂停的函数和方法在恢复运行所需要的信息
  • 例如，如果函数foo调用了函数goo，那么至少必须保存在函数goo结束时foo将要继续执行的指令的地址

二、指令空间

• 程序所需要的指令空间的数量取决于如下因素：
  • ①把程序编译成机器代码的编译器
  • ②编译时实际采用的编译器选项
  • ③目标计算机
• 在决定最终代码需要多少空间的时候，编译器是一个最重要的因素
• 编译器的覆盖选项：另外一种可以显著减少程序空间的编译器选项就是覆盖选项，在覆盖模式下，空间仅分配 给当前正在执行的程序模块。在调用一个新的模块时，需要从磁盘或其他设备中读取，新模块 的代码将覆盖原模块的代码。所以程序空间就等价于最大的模块所需要的空间（而不是所有模 块之和）
• 目标计算机的配置也会影响编译后的代码大小。如果计算机具有浮点处理硬件，那么每个浮点操 作可以转换成一条机器指令。如果没有安装浮点处理硬件，就需要生成代码来模拟浮点操作

演示说明

• 下图给出了用来计算表达式a+b+b*c+(a+b-c)/(a+b)+4的三段可能的代码，它们所需要的空间不一样。每一个代码都由相应的编译器产生

• 即使采用相同的编译器，所产生程序代码的大小也可能不一样。例如，一个编译器可能为用户提供优化选项，如代码优化以及执行时间优化等。比如，在上图中，在非优化模式下， 编译器可以产生b所示的代码。在优化模式下，编译器可以利用知识a+b+b*c=b*c+(a+b)来产生图中c中更短、更高效的代码。不过，使用优化模式通常会增加程序编译所需要的时间
• 从上图的例子中可以看到，一个程序还可能需要其他额外的空间，即诸如临时变量t1,t2,...,t6所占用的空间

三、数据空间

• 对各种数据类型，C++语言并没有指定它们的空间大小，只是大多数C++编译器有相应的空间分配
• 如下图所示，定义了32位计算机下的各种变量和常量所占用的空间（一个整形数据空间的大小与一个字的空间大小一样）

• 一个结构变量的空间大小是每个结构成员所需的空间大小之和。类似的，一个数组的空间大小是数组的长度乘以一个数组元素的空间代大小

四、环境栈空间

• 在开始性能分析时，分析员通常会忽略环境栈所需要的空间，因为他们不理解函数（尤其是递归函数）是如何被调用的以及在函数调用结束时会发生什么。每当一个函数被调用时，下面的数据将被保存在环境栈中：
  • ①返回地址
  • ②正在调用的函数的所有局部变量的值以及形式参数的值（仅对递归函数而言）
• 我们以下面的程序为例，每当其被调用时，不管调用来自函数外部还是内部，a和n的当前值以及调用结束时程序的断口地址都被存储在环境栈中

• 值得注意的是，有些编译器，不论对递归函数还是非递归函数，在函数调用时，都会保留局部变量的值和形参的值。而有些编译器则仅为递归函数保存上述内容。所以实际使用的编译器将影响环境栈所需要的空间

五、实例特性

• 程序要处理的问题实例都有一些特性。一 般来说，这些特征包含决定程序空间大小的因素（如，输入和输出的数量或相关数的大小）
• 例如，对于一个对n个元素进行排序的程序，可以确定该程序所需要的空间为 n 的函数；对于 一个累加两个n×n 矩阵的程序，可以使用n 作为其实例特征；而对于累加两个 m×n 矩阵的程序，可以使用m和n作为实例特征
• 实例特性与影响程序空间复杂度的关系：
  • 相对来说，指令空间的大小受实例特性的影响不大。常量及简单变量所需要的数据空间也与实例特性没有多大关系，除非相关数的大小对于所选定的数据类型来说实在太大，这时，要么改变数据类型，要么使用多精度算法重写该程序，然后再对新程序进行分析
  • 一些动态分配空间也可以不依赖实例特性。环境栈的大小一般不依赖实例特性，除非正在使用递归函数。在使用递归函数时，实例特征通常（但不总是）会影响环境栈的大小
• 函数的递归空间：递归函数所需要的栈空间通常称之为递归栈空间（ recursion stack space）。该空间主要依赖于局部变量及形式参数所需要的空间。除此以外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次）和编译器。如下左图的嵌套递归调用一直进行到n=0，嵌套调用的层次关系如下面有图所示，最大的递归深度是n+1。智能编译器可以把尾递归转换为迭代，从而减少，甚至排除递归栈空间

• 可以把一个程序所需要的空间分成两部分：
  • 固定部分：它独立于实例的特征。一般来说，这一部分包含指令空间（即代码空间）、简 单变量及定长复合变量所占用空间、常量所占用空间等等。
  • 可变部分：它由以下部分构成：复合变量所需的空间（这些变量的大小依赖于所解决的 具体问题），动态分配的空间（这种空间一般都依赖于实例的特征），以及递归栈所需的空间 （该空间也依赖于实例的特征）。
• 任意程序P所需要的空间S（P）可以表示为：
  • 其中c 是一个常量，表示固定部分所需要的空间， Sp表示可变部分所需要的空间。一个精确的分析还应当包括在编译期间所产生的临时变量所需要的空间（如文本的第一张图片所示），这种空 间是与编译器直接相关的，除依赖于递归函数外，它还依赖于实例的特征。本书将忽略这种空间

• 在分析程序的空间复杂性时，我们将把注意力集中在估算 Sp（实例特征）上。对于任意给定的问题，首先需要确定实例的特征以便于估算空间需求。实例特征的选择是一个很具体的问题，我们将求助于介绍各种可能性的实际例子。一般来说，我们的选择仅限于程序输入和输出的规模。有时我们也会对数据项之间的关系进行复杂的估算

六、演示案例

演示①

• 下面的程序。在计算Sp之前，必须选择实例特性。假定我们用a、b、c值的大小作为实例特性。因为abc是整型，所以每一个都占用4字节。另外，需要的空间是指令空间。因为数据空间和指令空间都不受abc值的大小所影响，所以Sabc（实例特性）=0

演示②

演示③

演示④

演示⑤

演示⑥