空间复杂性

运行完一个程序所需要的内存大小

程序的空间复杂性（space complexity）是指运行完一个程序所需要的内存大小，是计算机算法分析的重要概念之一，可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。

简介

空间复杂性(space complexity)计算机算法分析的重要概念之一，是计算中所需的存储空间资源耗费量的估计。如果一个问题的大小为n，解这个问题的某一算法所需的辅助存储空间为n的某个函数S(n)，则称S (n)为该算法的空间复杂性。例如，n个整数的分类问题，当用归并分类算法时，空间复杂性为O(n)，当用直接插入分类算法时，空间复杂性为O(1)(一个与n无关的常数)。

研究背景

程序性能

程序性能（program performance），是指运行一个程序所需要的内存大小和时间。

可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行性能分析（performance analysis）时，采用分析的方法，而在进行性能测量（performance measurement）时，借助于实验的方法。

研究原因

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

·如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。

·对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。

·一个问题可能有若干个内存需求各不相同的解决方案。

·可以利用空间复杂性来估算一个程序所能解决的问题的最大规模

空间复杂性的组成

程序所需要的空间主要由以下部分构成：

·指令空间（instruction space）指令空间是指用来存储经过编译之后的程序指令所需的空间。

·数据空间（data space）数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成：存储常量和简单变量所需要的空间；存储复合变量所需要的空间，这一类空间包括数据结构所需的空间及动态分配的空间。

·环境栈空间（environment stack space）环境栈用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数fun1调用了函数fun2，那么至少必须保存fun2结束时fun1将要继续执行的指令的地址。

指令空间

程序所需要的指令空间的数量取决于如下因素：

·把程序编译成机器代码的编译器。

·编译时实际采用的编译器选项。

·目标计算机

在决定最终代码需要多少空间的时候，编译器是一个最重要的因素。图给出了用来计算表达式a + b + b * c + ( a + b - c ) / ( a + b ) + 4的三段可能的代码，它们都执行完全相同的算术操作（如每个操作符都有相同的操作数），但每段代码所需要的空间都不一样。所使用的编译器将确定产生哪一种代码

另外一种可以显著减少程序空间的编译器选项就是覆盖选项，在覆盖模式下，空间仅分配给当前正在执行的程序模块。在调用一个新的模块时，需要从磁盘或其他设备中读取，新模块的代码将覆盖原模块的代码。所以程序空间就等价于最大的模块所需要的空间（而不是所有模块之和）。

目标计算机的配置也会影响代码的规模。如果计算机具有浮点处理硬件，那么每个浮点操作可以转换成一条机器指令。如果没有安装浮点处理硬件，必须生成仿真的浮点计算代码。

数据空间

对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。之所以如此是因为我们通常关心所需内存的字节数。由于每字节所占用的位数依赖于具体的机器环境，因此每个变量所需要的空间也会有所不同。此外，存储2100也将比存储23需要更多的位数。

环境栈

在刚开始从事性能分析时，分析员通常会忽略环境栈所需要的空间，因为他们不理解函数是如何被调用的以及在函数调用结束时会发生什么。每当一个函数被调用时，下面的数据将被保存在环境栈中：

·返回地址。

·函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）。

·所有引用参数及常量引用参数的定义。

每当递归函数被调用时，不管该调用是来自外部或a的当前赋值、n的值以及程序运行结束时的返回地址都被存储在环境栈之中。

值得注意的是，有些编译器在保留局部变量的值、传值形式参数的值以及引用参数和常量引用参数的定义时，对于递归函数和非递归函数一视同仁，而有些编译器则仅为递归函数保存上述内容。所以实际使用的编译器将影响环境栈所需要的空间。

全国各地天气预报查询