0-2 运行时间的计算方法

了解输入数据的量和运行时间之间的关系

上一节在结尾说明了算法的不同会导致其运行时间产生大幅变化，本节将讲解如何求得算法的运行时间。

使用相同的算法，输入数据的量不同，运行时间也会不同。比如，对10个数字排序和对1000000个数字排序，大家很容易就想到后者的运行时间更长。那么，实际上运行时间会长多少呢？后者是前者的100倍，还是1000000倍？就像这样，我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。

如何求得运行时间

那么，如何测算不同输入所导致的运行时间的变化程度呢？最为现实的方法就是在计算机上运行一下程序，测试其实际花费的时间。但是，就算使用同样的算法，花费的时间也会根据所用计算机的不同而产生偏差，十分不便。

所以在这里，我们使用“步数”来描述运行时间。“1步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。

作为示例，现在我们试着从理论层面求出选择排序的运行时间。选择排序的步骤如下。

如果数列中有n个数字，那么①中“寻找最小值”的步骤只需确认n个数字即可。这里，将“确认1个数字的大小”作为操作的基本单位，需要的时间设为Tc，那么步骤①的运行时间就是n×Tc。

接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为Ts。那么，①和②总共重复n次，每经过“1轮”，需要查找的数字就减少1个，因此总的运行时间如下。

虽说只剩最后1个数字的时候就不需要确认了，但是方便起见还是把对它的确认和交换时间计算在内比较好。

运行时间的表示方法

虽说我们已经求得了运行时间，但其实这个结果还可以简化。Tc和Ts都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度n，所以接下来考虑n变大的情况。n越大，上式中的n2也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是n2。所以，我们删掉其他部分，将结果表示成下式右边的形式。

通过这种表示方法，我们就能大致了解到排序算法的运行时间与输入数据量n的平方成正比。

同样地，假设某个算法的运行时间如下。

5Tx n3+12 Ty n2+3 Tz n

那么，这个结果就可以用O（n3）来表示。如果运行时间为

3nlog n+2 Ty n

这个结果就可以用O（nlogn）来表示。

O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”，准确的定义请参考相关专业书籍。重点在于，通过这种表示方法，我们可以直观地了解算法的时间复杂度。

比如，当我们知道选择排序的时间复杂度为O（n2）、快速排序的时间复杂度为O（nlogn）时，很快就能判断出快速排序的运算更为高速。二者的运行时间根据输入n产生的变化程度也一目了然。

关于算法的基本知识就介绍到这里了。从下一章开始，我们就来具体学习各种算法吧。