1-3　程序执行的时间测量方法：时间复杂度

1-3-1　基本概念

现在程序语言的功能很强，我们可以使用程序语言的时间函数记录一个程序执行所需的时间，这种方法最大的缺点是程序执行的时间会随着计算机的不同有所差异，所以绝对时间概念一般不被计算机科学家采用。

程序运行时间的测量方法是采用步骤数表示程序的运行时间，基本测量单位是1个步骤，由步骤数测量程序执行所需时间，我们又将此步骤数称时间复杂度。

　时间测量场景1

假设骑自行车每2分钟可以骑1千米，请问骑10千米的路需要多少时间？

答案是2 * 10，相当于需要20分钟。

假设想骑n千米，就需要2n分钟。

在时间测量方法中，我们可以使用T（ ）函数表达所需时间，骑n千米所需时间可以用下列数学公式表达：

T(n) = 2n

　时间测量场景2

假设有16千米的路段，骑自行车每3分钟可以骑剩下路程的一半，请问骑剩1千米需要多少时间？

第1个3分钟可以骑8千米，第2个3分钟可以骑4千米，第3个3分钟可以骑2千米，第4个3分钟可以骑1千米，可以用对数log表达这个解答。

3 * log216

下面笔者将log的底数2省略，所以表达式是3 * log16，此外，可以像一般数学公式一样省略乘法*符号，即简化为3log16，结果是12分钟。

假设距离n千米，则骑剩1千米需要3log n分钟，可以用下列数学公式表达：

T(n) = 3log n

使用Python可以用import math方式导入模块math，计算log的值，语法如下：

math.log(x[，base])    # base预设是e

参数base预设是e（约2.718281828459），对于其他底数，则须在第2个参数指出底数，所以对于底数是2，公式如下：

math.log(x，2)

实例1：计算3*log16的结果。

另外，math模块也可以使用log2（ ）方法处理底数为2的对数、使用log10（ ）方法处理底数为10的对数。

实例2：重复实例1，计算3*log16的结果。

　时间测量场景3

假设骑自行车第1千米需要1分钟，第2千米需要2分钟，第3千米需要3分钟，相当于每一千米所需时间比前1千米多1分钟，请问骑10千米需要多少时间？

上述答案是1+2+ … + 10，可以得到55，所以需要55分钟。

如果距离是n千米，则所需时间计算方式如下：

1 + 2 + … + (n-1) + n

其实这也是1-2-2节选择排序方法所述的数学公式，我们也可以用下列数学公式表达：

T(n) = 0.5n2+0.5n

　时间测量场景4

假设骑自行车每2分钟可以骑1千米，喝一杯饮料需要2分钟，请问喝一杯饮料需要多少时间？

此问题与骑自行车无关，答案是2分钟。

假设要骑的距离是10千米，喝一杯饮料需要多少时间？

此问题依旧与骑自行车无关，答案是2分钟，所以可以用下列数学公式表达所需时间，这是一个常数的结果：

T(n) = 2

1-3-2　时间测量复杂度

在计算机科学领域，实际上是将程序执行的时间测量简化为一个数量级数，简化的结果也称时间复杂度，此时间复杂度使用O（f（n））表示，一般将O念作Big O，也称Big O表示法。

简化的原则如下：

　时间复杂度简化原则1

如果时间复杂度是常数，用1表示，则1-3-1节的时间测量场景4的T（n）=2可以用下列方式表达：

T(n) = O(1)

　时间复杂度简化原则2

省略系数，所以1-3-1节的时间测量场景1的T（n） = 2n可以用下列概念方式表达：

T(n) = O(n)

1-3-1节的时间测量场景2的T（n）=3log n可以用下列方式表达：

T(n) = O(log n)

　时间复杂度简化原则3

保留最高阶项目，同时也省略系数，所以1-3-1节的时间测量场景3的T（n）=0.5n2+0.5n可以先省略低阶0.5n，再省略最高阶系数0.5，结果如下：

T(n) = O(n2)

当n值够大时，在上述执行的时间复杂度结果，我们必须知道相对时间关系如下：

O(1) < O(log n) < O(n) < O(n2)

由于O（n2）的时间效率相较前3个差很多，所以下列实例笔者先用程序做说明。

程序实例ch1_4.py：用程序绘制O（1）、O（log n）、O（n）的图形，对比当n从1变到10时，所需要的程序运行时间关系图。

执行结果

注　numpy模块在使用底数为2的对数log时，与math一样使用log2（ ）方法，可以参考上述第7行。

其实在程序时间测量中，另一个常会遇见的时间复杂度是O（nlog n），这个时间复杂度与先前的时间复杂度关系如下：

O(1) < O(log n) < O(n) < O(nlog n) < O(n2)

至于ch1_2.py使用枚举法列出所有排列组合，再找出从小到大的排列方式的时间复杂度是O（n!），则整个时间复杂度关系如下：

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n!)

程序实例ch1_5.py：用程序绘制O（1）、O（log n）、O（n）、O（nlog n）、O（n2）的图形，可以对比当n从1变到10时，所需要的程序运行时间关系图。

执行结果

注　其实我们也可以将执行算法时间复杂度所耗损的时间称时间成本。下表是当n是2、8、16时，假设设备每秒可以操作100次步骤，各种算法所需的时间。