文档介绍：第二章复杂性分析初步
程序性能(program performance)是指运行一个程序所需的内存大小和时
间多少。所以,程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主
要包含两方面,即性能分析(performance analysis)与性能测量(performance
measurement),前者采用分析的方法,后者采用实验的方法。
考虑空间复杂性的理由
在多用户系统中运行时,需指明分配给该程序的内存大小;
想预先知道计算机系统是否有足够的内存来运行该程序;
一个问题可能有若干个不同的内存需求解决方案,从中择取;
用空间复杂性来估计一个程序可能解决的问题的最大规模。
考虑时间复杂性的理由
某些计算机用户需要提供程序运行时间的上限(用户可接受的);
所开发的程序需要提供一个满意的实时反应。
选取方案的规则:如果对于解决一个问题有多种可选的方案,那么方案的
选取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂
性,最好采取加权的方式进行评价。但是随着计算机技术的迅速发展,对
空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强
调时间复杂性的分析。
§1 空间复杂性
程序所需要的空间:
指令空间-用来存储经过编译之后的程序指令。程序所需的指令空间的大小
取决于如下因素:
把程序编译成机器代码的编译器;
编译时实际采用的编译器选项;
目标计算机。
所使用的编译器不同,则产生的机器代码的长度就会有差异;有些编译器带
有选项,如优化模式、覆盖模式等等。所取的选项不同,产生机器代码也会不同。
此外,目标计算机的配置也会影响代码的规模。例如,如果计算机具有浮点处理
硬件,那么,每个浮点操作可以转化为一条机器指令。否则,必须生成仿真的浮
点计算代码,使整个机器代码加长。一般情况下,指令空间对于所解决的特定问
题不够敏感。
数据空间-用来存储所有常量和变量的值。分成两部分:a).存储常量和简
单变量;b).存储复合变量。前者所需的空间取决于所使用的计算机和编译
器,以及变量与常量的数目,这是由于我们往往是计算所需内存的字节数,
而每个字节所占的数位依赖于具体的机器环境。后者包括数据结构所需的空
间及动态分配的空间。
类型占用字节数适用范围
char 1 -128~127
unsigned char 1 0~255
short 2 -32768~32 767
int 2 -32768~32 767
unsigned int 2 0~65 535
long 4 -2 31~2 31-1
unsigned long 4 0~2 31-1
float 4 ± ±38
double 8 ± ±308
long double 10 -4932~ +4932
pointer 2 (near,_cs,_ds,_es,_ss 指针)
pointer 4 (far, huge 指针)
在 16 位计算机上,Borland C++中各种变量所占空间
计算方法:结构变量所占空间等于各个成员所占空间的累加;数组变量所占
空间等于数组大小乘以单个数组元素所占的空间。例如
double a[100]; 所需空间为 100×8=800
int matrix[r][c]; 所需空间为 2×r×c
环境栈空间-保存函数调用还回时恢复运行所需要的信息。当一个函数被调
用时,下面数据将被保存在环境栈中:
返回地址;
所有局部变量的值、递归函数的传值形式参数的值;
所有引用参数以及常量引用参数的定义。
在分析空间复杂性中,实例特征的概念非常重要。所谓实例特征是指决定问
题规模的那些因素。如,输入和输出的数量或相关数的大小,如对 n 个元素进行
排序、n×n 矩阵的加法等,都可以 n 作为实例特征,而两个 m×n 矩阵的加法应
该以n和m两个数作为实例特征。
指令空间的大小对于所解决的待定问题不够敏感。常量及简单变量所需要的
数数据空间也独立于所解决的问题,除非相关数的大小对于所选定的数据类型来
说实在太大。这时,要么改变数据类型要么使用多精度算法重写该程序,然后再
对新程序进行分析。
复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独
立于实例的特征,除非正在使用递归函数。在使用递归函数时,实例特征通常会
影响环境栈所需要的空间数量。
递归函数所需要的栈空间主要依赖