1.4.1 空间复杂性

算法的空间复杂性是指计算机执行一个算法所需占用的存储空间，它是算法优劣的重要度量指标。一般地，空间复杂性程度越低，算法越好。算法执行需要的空间包括指令空间、数据空间和系统栈空间三大类。

指令空间用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素：① 把程序编译成机器代码的编译器；② 编译时实际采用的编译器选项；③ 目标计算机。程序编译时使用的编译器不同，产生的机器代码的长度就会有差异。另外，有些编译器带有选项，如优化模式、覆盖模式等，如果设置的编译选项不同，产生的机器代码也会不同。当然，目标计算机的配置也会影响代码的规模。例如，如果计算机具有浮点处理的硬件部件，那么每个浮点操作可以转化为一条机器指令；否则，必须生成仿真的浮点计算代码，使整个机器代码加长。一般情况下，指令空间对于所解决的特定问题不够敏感，以至于可以忽略不计。

数据空间用来存储所有常量和变量的值，分成两部分：① 存储常量和简单变量；② 存储复合变量。前者所需的空间取决于所使用的计算机和编译器，以及变量与常量的数目。因为人们往往是计算所需内存的字节数，而每字节所占的位（bit）依赖于具体的机器环境（16位字长计算机中C/C++各数据类型及取值范围参见表2-1）。后者包括数据结构所需的空间及动态分配的空间。结构变量所占空间等于各成员所占空间的累加，数组变量所占空间等于数组大小乘以单个数组元素所占的空间。

系统栈空间保存函数调用返回时恢复运行所需要的信息。当一个函数被调用时，下面数据将被保存在系统栈中：① 返回地址；② 所有局部变量的值、递归函数的传递的形式参数的值；③ 所有引用参数以及常量引用参数的定义。对于递归程序调用，系统栈空间大小还依赖于递归调用的深度，而且这往往是决定系统栈空间大小的主要因素。

程序1-1为数组求和程序（本书采用C/C++编程，下同）。

程序1-1 数组求和程序

在程序1-1中，函数sum1采用循环累加的办法，而函数sum2采用递归的办法。在sum1中，int型变量i、iSum、iLen各自需要分配4字节（在16位字长计算机为2字节）的内存空间，指针型参数iArray需要分配4字节的内存空间。在sum2中，递归栈空间包括参数iArray、iLen所需的8字节，以及保存返回地址所需的2字节（假定是near指针）。每次调用sum2就需要10字节空间，假定某个实例的递归深度是n，则共需10×(n+1)字节的内存空间。

随着半导体技术的飞跃式发展，存储器资源的成本越来越低，人们对于算法空间复杂性的关注度也越来越低。因此，本书后续章节分析算法的复杂性时，也忽略了空间复杂性分析。