1.3.2　時間復雜性

時間復雜性是對算法運行時間長短的度量。度量的方法通常有兩種：事后統計法和事前分析估算法。

1．事后統計法

因為很多計算機內部都有計時功能，有的甚至可以精確到毫秒，所以采用不同算法設計出的程序可通過一組或若干組相同的統計數據分辨優劣。

但該方法有兩種缺陷：一是必須先運行依據算法編寫的程序；二是所得時間的統計量依賴于計算機的硬件、軟件等環境因素，有時會掩蓋算法本身的優劣。因此，人們常常不采用該方法進行時間復雜性分析。

2．事前分析估算法

與算法的運行時間相關的因素通常有問題的規模、算法的輸入序列、算法選用的設計策略、編寫程序的語言、編譯程序產生的機器代碼的質量及計算機執行指令的速度等。

顯然，在各種因素都不能確定的情況下，將很難估算出算法的運行時間，可見使用運行算法的絕對時間來衡量算法的效率是不現實的。如果撇開這些與計算機硬、軟件有關的因素，一個特定算法的運行時間將只依賴于問題的規模（通常用正整數n表示）和它的輸入序列I。因此，算法的運行時間可表示為二者的函數，記為T（n，I）。

通常情況下，人們只考慮3種情況下的時間復雜性，即最壞情況、最好情況和平均情況，并分別記為T_max（n）、T_min（n）和T_avg（n）。設D_n是問題規模為n的算法的所有合法輸入序列集合；I0是使算法的時間效率達到最差的合法輸入序列集合；I1是使算法的時間效率達到最好的合法輸入序列集合；P（I）是算法在應用中出現輸入序列I的概率。在數學上有

由此，針對特定的輸入序列，算法的時間復雜性只與問題的規模n有關。一個不爭的事實是：幾乎所有的算法，規模越大所需的運行時間就越長。當n不斷變化時，運行時間也會不斷變化，故人們通常將算法的運行時間記為T（n）。