0-2 運行時間的計算方法

了解輸入數據的量和運行時間之間的關系

上一節在結尾說明了算法的不同會導致其運行時間產生大幅變化，本節將講解如何求得算法的運行時間。

使用相同的算法，輸入數據的量不同，運行時間也會不同。比如，對10個數字排序和對1000000個數字排序，大家很容易就想到后者的運行時間更長。那么，實際上運行時間會長多少呢？后者是前者的100倍，還是1000000倍？就像這樣，我們不光要理解不同算法在運行時間上的區別，還要了解根據輸入數據量的大小，算法的運行時間具體會產生多大的變化。

如何求得運行時間

那么，如何測算不同輸入所導致的運行時間的變化程度呢？最為現實的方法就是在計算機上運行一下程序，測試其實際花費的時間。但是，就算使用同樣的算法，花費的時間也會根據所用計算機的不同而產生偏差，十分不便。

所以在這里，我們使用“步數”來描述運行時間。“1步”就是計算的基本單位。通過測試“計算從開始到結束總共執行了多少步”來求得算法的運行時間。

作為示例，現在我們試著從理論層面求出選擇排序的運行時間。選擇排序的步驟如下。

如果數列中有n個數字，那么①中“尋找最小值”的步驟只需確認n個數字即可。這里，將“確認1個數字的大小”作為操作的基本單位，需要的時間設為Tc，那么步驟①的運行時間就是n×Tc。

接下來，把“對兩個數字進行交換”也作為操作的基本單位，需要的時間設為Ts。那么，①和②總共重復n次，每經過“1輪”，需要查找的數字就減少1個，因此總的運行時間如下。

雖說只剩最后1個數字的時候就不需要確認了，但是方便起見還是把對它的確認和交換時間計算在內比較好。

運行時間的表示方法

雖說我們已經求得了運行時間，但其實這個結果還可以簡化。Tc和Ts都是基本單位，與輸入無關。會根據輸入變化而變化的只有數列的長度n，所以接下來考慮n變大的情況。n越大，上式中的n2也就越大，其他部分就相對變小了。也就是說，對式子影響最大的是n2。所以，我們刪掉其他部分，將結果表示成下式右邊的形式。

通過這種表示方法，我們就能大致了解到排序算法的運行時間與輸入數據量n的平方成正比。

同樣地，假設某個算法的運行時間如下。

5Tx n3+12 Ty n2+3 Tz n

那么，這個結果就可以用O（n3）來表示。如果運行時間為

3nlog n+2 Ty n

這個結果就可以用O（nlogn）來表示。

O這個符號的意思是“忽略重要項以外的內容”，讀音同Order。O（n2）的含義就是“算法的運行時間最長也就是n2的常數倍”，準確的定義請參考相關專業書籍。重點在于，通過這種表示方法，我們可以直觀地了解算法的時間復雜度。

比如，當我們知道選擇排序的時間復雜度為O（n2）、快速排序的時間復雜度為O（nlogn）時，很快就能判斷出快速排序的運算更為高速。二者的運行時間根據輸入n產生的變化程度也一目了然。

關于算法的基本知識就介紹到這里了。從下一章開始，我們就來具體學習各種算法吧。