1.3.2　时间复杂性

时间复杂性是对算法运行时间长短的度量。度量的方法通常有两种：事后统计法和事前分析估算法。

1．事后统计法

因为很多计算机内部都有计时功能，有的甚至可以精确到毫秒，所以采用不同算法设计出的程序可通过一组或若干组相同的统计数据分辨优劣。

但该方法有两种缺陷：一是必须先运行依据算法编写的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时会掩盖算法本身的优劣。因此，人们常常不采用该方法进行时间复杂性分析。

2．事前分析估算法

与算法的运行时间相关的因素通常有问题的规模、算法的输入序列、算法选用的设计策略、编写程序的语言、编译程序产生的机器代码的质量及计算机执行指令的速度等。

显然，在各种因素都不能确定的情况下，将很难估算出算法的运行时间，可见使用运行算法的绝对时间来衡量算法的效率是不现实的。如果撇开这些与计算机硬、软件有关的因素，一个特定算法的运行时间将只依赖于问题的规模（通常用正整数n表示）和它的输入序列I。因此，算法的运行时间可表示为二者的函数，记为T（n，I）。

通常情况下，人们只考虑3种情况下的时间复杂性，即最坏情况、最好情况和平均情况，并分别记为T_max（n）、T_min（n）和T_avg（n）。设D_n是问题规模为n的算法的所有合法输入序列集合；I0是使算法的时间效率达到最差的合法输入序列集合；I1是使算法的时间效率达到最好的合法输入序列集合；P（I）是算法在应用中出现输入序列I的概率。在数学上有

由此，针对特定的输入序列，算法的时间复杂性只与问题的规模n有关。一个不争的事实是：几乎所有的算法，规模越大所需的运行时间就越长。当n不断变化时，运行时间也会不断变化，故人们通常将算法的运行时间记为T（n）。