首页 > Python算法 > 认识算法 阅读数:33

计算时间复杂度究竟有什么意义?

计算时间复杂度的意义在于何处呢?读者或许认为,两个不同算法的时间复杂度的差距还没有刚才所提到的优化算法优化的程度高,但其实如果输入规模极为庞大,时间复杂度的差距能使计算机运算的效率提升很多个数量级。

以经典的排序算法为例。简单、基础的插入排序算法,其时间复杂度是 O(n2)。但有更高效的算法可以解决排序问题,如归并排序(后面将详细介绍),其时间复杂度为 O(nlgn)。

如图 1 所示,实线代表 n2,虚线代表 nlgn。
时间复杂度
图 1:时间复杂度

从图 1 中可以基本看出 n和 nlgn 的增长趋势。当 n=1000 时,lgn 大致为 3,nlgn 大致为 3000,而 n=1000000 时,lgn 大致为 6,nlgn 大致为 6000000。如此看来结果一目了然,当输入的规模较小时,插入排序通常会比归并排序运行时间短,但当输入规模逐渐增大时,归并排序的速度将远超插入排序。

举一个具体的例子,我们现在用两台完全相同的计算机甲和乙,分别运行插入排序和归并排序来解决输入规模为 1000万 的排序问题(这 1000 万个数都会是 8 字节的整数,并存在一个数组或列表中;而总的输入所需的存储空间大约 80MB,完全不会影响一台计算机的运算效率)。

假设两台计算机每秒能执行 1000 亿条指令;同时假设使用计算机甲的程序员巧妙地使用机器语言实现插入排序,结果整个代码需要 2n2 条指令的运算。使用计算机乙的程序员仅使用普通的高级语言来编写归并排序,整个代码需要执行 50nlgn 条指令的运算。

在这种情况下,为了排序这 1000 万个数,使用插入排序的计算机甲需要:

2 x {(107)2条指令/(1010)条指令/秒}=2 x 104秒≈5.6小时


而使用归并排序的计算机乙需要:

50 x {(107lg107)条指令/(1010)条指令/秒}=0.35秒


显然,运行时间的差距是复杂度前的常数因子无法弥补的。而如上所示的只是输入规模为 1000 万的情况,运行时间差距之大不言自明。若是输入规模为 1 亿或 10 亿呢?这两个算法的运行时间差距就会让人讶异。一般来说,随着输入规模的增大,时间复杂度越低的算法的优势越明显。

虽然时间复杂度可以定量地描述出一个算法的复杂度,但时间复杂度在一定情况下是会变化的。比如说,如果运用快速排序算法来对一序列数进行排序,时间复杂度会因原始的输入序列不同而改变,输入序列与排序后的序列越接近,更改元素位置的次数越少,时间复杂度越小。