程序性能1--空间复杂性

阅读《数据结构算法与应用：C++描述》第二章程序性能所做的笔记。

第2章程序性能的所有笔记如下：

介绍

程序性能：是指运行一个程序所需要的内存大小和时间。
可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行性能分析(performance analysis)时，采用分析的方法；而在进行性能测量(performance measurement)时，借助于实验的方法。

程序的空间复杂性是指运行完一个程序所需要的内存大小。

程序的时间复杂性是指运行完该程序所需要的时间。

空间复杂性

空间复杂性的组成

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

指令空间：是值用来存储经过编译之后的程序指令所需要的空间。
数据空间：是指用来存储所有常量和变量值所需的空间。其主要由两个部分构成：
- 存储常量和简单变量所需要的空间
- 存储复合变量所需要的空间。这一类空间包括数据结构所需要的空间动态分配的空间
环境栈空间：用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数fun1调用了函数fun2，那么至少必须保存fun2结束时fun1将要继续执行的指令的地址。

指令空间

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

把程序编译成机器代码的编译器；
编译时实际采用的编译器选项；
- 目标计算机。

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

即使采用相同的编译器，所产生程序代码的大小也可能不一样。例如，一个编译器可能为用户提供优化选项，如代码优化以及执行时间优化等。如，在图2-1中，非优化模式下，编译器可以产生图2-1b的代码，而优化模式下，则会产生图2-1c中更短更高效的代码。使用优化模式通常会增加程序编译所需要的时间。

另一种可以显著减少程序空间的编译器选项就是覆盖选项

覆盖模式：空间仅分配给当前正在执行的程序模块，在调用一个新的模块时，需要从磁盘或从其他设备中读取，新模块的代码将覆盖原模块的代码。所以程序的空间就等价于最大的模块所需要的空间，而不是所有模块之和。

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

数据空间

对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。

对于一个结构变量，可以把它的每个成员所占用的空间累加起来即可得到该变量所需要的内存。类似地，可以得到一个数组变量所需要的空间，方法是用数组的大小乘以单个数组元素所需要的空间。

比如对于double a[100];，数组a需要的空间是100个double类型元素所占用的空间，若每个元素占用8个字节，则分配给数组的空间总量为800字节。

环境栈

每当一个函数被调用时，下面的数据将被保存在环境栈中：

返回地址
函数被调用时所有局部变量的值以及传值形式参数的值(仅对于递归函数而言)
- 所有引用参数及常量引用参数的定义。

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

小结

指令空间的大小对于所解决的特定问题不够敏感。常量及简单变量所需要的数据空间也独立于所解决的问题，除非相关数的大小对于所选定的数据类型来说实在太大，这时，要么改变数据类型，要么使用多精度算法重写该程序，然后再对新程序进行分析。
复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独立于实例的特征，除非正在使用递归函数。在使用递归函数时，实例特征通常(但不总是)会影响环境栈所需要的空间数量。

实例的特征包含决定问题规模的因素，如输入输出的数量或相关数的大小。例如，对于一个对n个元素进行排序的程序，可以确定该程序所需要的空间为n的函数；

因此，可以把一个程序所需要的空间分成两部分：

固定部分，它独立于实例的特征。一般来说，这一部分包含指定空间(即代码空间)、简单变量及定长复合变量所占用空间、常量占用空间等；

可变部分，它由以下部分构成：复合变量所需的空间(这些变量的大小依赖于所解决的具体问题)，动态分配的空间(这种空间一般都依赖于实例的特征)，以及递归栈所需要的空间(该空间也依赖于实例的特征).

任意程序P所需要的空间S(P)可以表示为：
$S(P) = c + S_p(实例特征)$
其中c是一个常量，表示固定部分所需要的空间，而$S_p$表示可变部分所需要的空间。一个精确的分析还应当包括在编译期间所产生的临时变量所需要的空间，这种空间是与编译器直接相关的，除依赖于递归函数外，它还依赖于实例的特征。
在分析程序的空间复杂性时，我们将把注意力集中在估算$S_p$(实例特征)上。对于任意给定的问题，首先需要确定实例的特征以便于估算空间需求。一般，实例特征的选择会受到相关数的数量以及程序输入和输出的规模的限制。

举例

这里举例说明，例子如下：

[顺序搜索] 下列程序从左至右检查数组a[0:n-1]中的元素，以查找与x相等的那些元素。如果找到一个元素与x相等，则函数返回x第一次出现所在的位置。如果在数组中没有找到这样的元素，函数返回-1.

/*在未排序的数组 a [ 0 : n-1 ]中搜索 x
  如果找到，则返回所在位置，否则返回- 1*/
template<class T>
int SequentialSearch(T a[], const T& x, int n)
{
    int i;
    for (i = 0; i < n && a[i] != x; i++);
    if (i == n) return -1;
    return i;
}

我们希望采用实例特征n来估算该函数的空间复杂性。假定T是int类型，则数组a中的每个元素需要2个字节，实例x需要2个字节，传值形式参数n也需要2个字节，局部变量i需要2个字节，每个整型常量0和-1也分别需要2个字节。因此，所需要的总的数据空间是12字节，因为该空间独立于n，所以$S_{顺序搜索}$(n) = 0.

注意数组a必须足够大以容纳所查找的n个元素。不过，该数组所需要的空间已在定义实际参数(对应于a)的函数中分配，所以不需要把该数组所需要的空间加到上述函数SequentialSearch所需要的空间上去。