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.5n ² +0.5n 可以先省略低阶 0.5n ，再省略最高阶系数 0.5 ，结果如下：

     T(n) = O(n2)

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

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

由于O（n ² ）的时间效率相较前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（n ² ）的图形，可以对比当n从1变到10时，所需要的程序运行时间关系图。

执行结果

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