计算算法的运行时间

算法的不同会导致其运行时间产生大幅变化。
使用相同的算法，输入数据的量不同，运行时间也会不同。比如，对10 个数字排序和对1 000 000 个数字排序，很容易就想到后者的运行时间更长。

那么，实际上运行时间会长多少呢？后者是前者的100 倍，还是1 000 000 倍？就像这样，我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。

我们使用“步数”来描述运行时间。“1 步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。
作为示例，现在我们试着从理论层面求出选择排序的运行时间。选择排序的步骤如下。
① 从数列中寻找最小值
② 将最小值和数列最左边的数字进行交换，排序结束。回到①
如果数列中有n 个数字，那么①中“寻找最小值”的步骤只需确认n 个数字即可。这里，将“确认1 个数字的大小”作为操作的基本单位，需要的时间设为T_c，那么步骤①的运行时间就是n×T_c。
接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为T^s。那么，①和②总共重复n 次，每经过“1 轮”，需要查找的数字就减少1 个，因此总的运行时间如下。

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

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

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

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

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

 这个结果就可以用O(nlogn) 来表示。

O 这个符号的意思是“忽略重要项以外的内容”，读音同Order。O(n²) 的含义就是“算法的运行时间最长也就是n² 的常数倍”。

重点在于，通过这种表示方法，我们可以直观地了解算法的时间复杂度。
比如，当我们知道选择排序的时间复杂度为O(n²)、快速排序的时间复杂度为O(nlogn) 时，很快就能判断出快速排序的运算更为高速。

二者的运行时间根据输入n 产生的变化程度也一目了然。