1.2.5　算法的时间复杂度和空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n））。它表示随着问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐近时间复杂度（简称时间复杂度）。例如：

（1）{a=3；b=4；sum=a+b；}

（2）for（i=1；i<=n；i++）s+=x；

（3）for（i=1；i<=n；i++）

for（j=1；j<=n；j++）x=x+2；

3个程序段的时间复杂度分别为O（1）、O（n）、O（n2）。

有些情况下，算法中基本操作重复执行的次数随问题的输入数据的不同而不同，例如，对n个整数进行排序，此时取其平均时间复杂度。但当平均时间复杂度无法计算时，则取其最坏情况下的时间复杂度。

算法的空间复杂度一般是指执行这个算法所需要的内存空间，记作S（n）=O（g（n）），其中n为问题的规模，它表示随着问题规模n的增大，算法运行所需存储量的增长率与g（n）的增长率相同。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算机所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序外的辅助变量所占的额外空间，否则应同时考虑输入本身所需的空间（和输入数据的表示形式有关）。若所需的额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。