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次步驟，各種算法所需的時間。