2.6　算法评价

算法效率的度量通过时间复杂度和空间复杂度来描述。

1.时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数，算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数。时间复杂度主要分析T(n)的数量级，算法中的基本运算（最深层循环内的语句）的频度和T(n)同数量级，通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度，因此算法的时间复杂度记为“T(n)=O(f(n))”。

说明：上式中的“O”的含义是T(n)的数量级，其严格的数学定义是若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正整数C和N0，使得当N≥N0时都满足0≤T(n)≤C *f(n)。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）。

（1）最坏时间复杂度：指在最坏情况下算法的时间复杂度。

（2）平均时间复杂度：指所有可能输入实例在等概率出现的情况下算法的期望运行时间。

（3）最好时间复杂度：指在最好的情况下算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂度时有以下两条规则。

（1）加法规则。

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))。

（2）乘法规则。

T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))。

2.空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。渐进空间复杂度也常简称为“空间复杂度”，记为“S(n)=O(g(n))”。

一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外，也需要一些处理数据的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间是常量，即O(1)。