算法的時間復雜性

徐素梅

（安徽理工大學 理學院，安徽 淮南 232001）

一個算法是一個有限指令的集合。這些指令確定了解決某一問題的運算或操作程序。問題是要求回答的提問。通常有幾個參數或自變量，他們的值是特定的，取自問題的定義域，問題的描述即對其參數進行描述，之處其解是滿足什么性質的命題。給問題的全體參數都指定了確定的值，便得到問題的一個實例。例如“y+z=?”是加法問題，而”4+7=?”是加法實例。當然，一個問題一般可以包含多個實例。一個計算機程序即使是按照正確的算法編寫的，對于一些輸入來時也許是毫無用處的，因為這個程序的執(zhí)行時間太長，或者程序的數據、變量等占用的存儲空間太大。算法分析是指通過分析得到算法所需的時間和空間的估計量，算法的復雜度是指執(zhí)行算法所需的時間和空間的量。因此，本文敘述一下算法執(zhí)行所需時間的問題。

1 時間復雜性

圖1

用微積分可以證明，上列函數中給每個函數都小于其對于數字的函數，即每個函數與其后數字代表的函數的比在n無限增長時趨于0.圖1顯示了這些函數的圖像，圖1中函數值的每個刻度都是它前面刻度的兩倍。

1.1 時間頻度

一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數成正比例，哪個算法中語句執(zhí)行次數多，它花費時間就多。一個算法中的語句執(zhí)行次數稱為語句頻度或時間頻度。記為T(n)。

1.2 計算方法

a、一般情況下，算法的基本操作重復執(zhí)行的次數是模塊n的某一個函數 f（n），因此，算法的時間復雜度記做：T（n）=O（f（n））_

分析：隨著模塊n的增大，算法執(zhí)行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，算法的時間復雜度越低，算法的效率越高。

b、算法的時間復雜度

若要比較不同的算法的時間效率，受限要確定一個度量標準，最直接的辦法就是將計算法轉化為程序，在計算機上運行，通過計算機內部的計時功能獲得精確的時間，然后進行比較。但該方法受計算機的硬件、軟件等因素的影響，會掩蓋算法本身的優(yōu)劣，所以一般采用事先分析估算的算法，即撇開計算機軟硬件等因素，只考慮問題的規(guī)模（一般用用自然數n表示），認為一個特定的算法的時間復雜度，只采取于問題的規(guī)模，或者說它是問題的規(guī)模的函數。為了方便比較，通常的做法是，從算法選取一種對于所研究的問題（或算法模型）來說是基本運算的操作，以其重復執(zhí)行的次數作為評價算法時間復雜度的標準。該基本操作多數情況下是由算法最深層環(huán)內的語句表示的，基本操作的執(zhí)行次數實際上就是相應語句的執(zhí)行次數。一般T（n）=Of（n）

例如：

則有T（n）=n的平方+n的三次方，根據上面括號里的同數量級，我們可以確定 n的三次方為T（n）的同數量級

則有 f（n）=n 的三次方，然后根據 T（n）/f（n）求極限可得到常數 c則該算法的 時間復雜度：T（n）=O（n的三次方）

O（1）

1.3 分類

按數量級遞增排列，常見的時間復雜度有：

常數階 O（1），對數階 O（log2n），線性階 O（n），k 次方階 O（nk），指數階 O（2n）。隨著問題規(guī)模 n 的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行效率越低。

線性對數階 O（nlog2n），平方階 O（n2），立方階 O（n3），...，

假設是“標準”的計算機，算法的時間的復雜性的考慮可以在輸入規(guī)模一定的情況下，用算法使用的基本操作（解問題的關鍵操作，操作次數隨輸入規(guī)模的增大而增加）次數來表示。而不用計算機實際運行的時間來表示，這時因為執(zhí)行基本操作時，不同的計算機需要的時間不同，而且把所有運算分解成計算機使用的基本字位運算是相當復雜的。

在所有輸入規(guī)模為n的情況下，可以找到執(zhí)行算法所需的最短時間和最長時間，分別稱為輸入規(guī)模為n的最好時間復雜性和最壞時間復雜性。平均時間是指在一組有限的規(guī)模為n的輸入中執(zhí)行算法所需的時間。平均時間復雜性分析比最壞情況分析復雜的多。

圖2給出了描述算法時間復雜性的幾個常用術語

圖2

變量計數：

一般情況下，對步進循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數，忽略該語句中步長加1、終值判別、控制轉移等成分。因此，以上程序段中頻度最大的語句是（6），其頻度為f（n）=n2，所以該程序段的時間復雜度為T（n）=O（n2）。當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數最多的循環(huán)語句中最內層語句的頻度f（n）決定的。

2 空間復雜度

空間復雜度（Space Complexity）是對一個算法在運行過程中臨時占用存儲空間大小的量度。比如插入排序的時間復雜度是O（n2），空間復雜度是O（1）而一般的遞歸算法就要有O（n）的空間復雜度了,因為每次遞歸都要存儲返回信息

一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面衡量。 類似于時間復雜度的討論，一個算法的空間復雜度(SpaceComplexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數。漸近空間復雜度也常常簡稱為空間復雜度?？臻g復雜度(SpaceComplexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。

算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地”進行的，是節(jié)省存儲的算法，有的算法需要占用的臨時工作單元數與解決問題的規(guī)模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元。

分析一個算法所占用的存儲空間要從各方面綜合考慮。如對于遞歸算法來說，一般都比較簡短，算法本身所占用的存儲空間較少，但運行時需要一個附加堆棧，從而占用較多的臨時工作單元；若寫成非遞歸算法，一般可能比較長，算法本身占用的存儲空間較多，但運行時將可能需要較少的存儲單元。

空間復雜度與時間復雜度類似，空間復雜度是指算法在計算機內執(zhí)行時所需存儲空間的度量，作：S（n）=Of（n）。一個空間復雜度只考慮在運行過程中為局部變量分配的存儲空間的大小，它包括為參數表中形參變量分配的存儲空間和為在函數體中定義的局部變量分配的存儲空間兩個部分。若一個算法為遞歸算法，其空間復雜度為遞歸所使用的堆?？臻g的大小，它等于一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表不開始進行的一次非遞歸調用)。

漸進時間復雜度評價算法時間性能主要用算法時間復雜度的數量級（即算法的漸近時間復雜度）評價一個算法的時間性能

3 聯系

對于一個算法，其時間復雜度和空間復雜度往往是相互影響的。當求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間；反之，當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當設計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數據量的大小，算法描述語言的特性，算法運行的機器系統環(huán)境等各方面因素，才能夠設計出比較好的算法。算法的時間復雜度和空間復雜度合稱為算法的復雜度。

圖3 常用的算法的時間復雜度和空間復雜度

4 NPC問題

能使用具有多項式最壞情況復雜性的算法解決的問題稱為易處理的，否則，稱為不易處理的。不過，如果在大O估計中的多項式次數高（如100次），多項式的次數特別大，算法可能會花特別長的時間來解決問題。對于實際應用中出現的不易處理的問題，如果存在求近似解的快速算法，甚至還能保證近似解與精確解相差不太大，通常不求其精確解，而求其近似解。

易處理的問題屬于P問題，至今既沒有找到多項式算法，又不能證明它不存在多項式算法。這類問題稱為NPC問題。還有一類重要問題，只要其中任何一個問題能用一個多項式時間最壞情況算法解答，稱為其NPC問題簡稱NPC問題。

5 小結

隨著科學技術的不斷發(fā)展，計算機速度和內存空間獲得巨大的增長，再加上使用能做并行處理的算法，以前認為的不能同時兼顧時間復雜性和空間復雜性的問題將迅速的減少，極大的減少了計算機所花的時間和占有的存儲量，空間復雜性與實現算法時間使用的特定數據結構緊密相連，我相信在即將的未來隨著科學技術的不斷進步，一些繁復的NPC問題和極度復雜不能兼顧時間與空間的問題將面臨攻克。算法復雜度將不再是解問題的巨大障礙。

［1］卜月華，吳建專，顧國華，殷翔，圖論及其應用[M].東南大學出版社，2002.

［2］蔣長浩,圖論與網絡流[M].中國林業(yè)大學出版社，2001.

［3］殷劍宏,吳開亞.[M]中國科學技術大學出版社，2003

［4］Back T，Schwefel H P.An overview of evolutionary algorithms for parameter optimization[J].Evolutionary Computation.1993.

［5］Fogel L J，Owens A J，Walsh M J.Artificial Intelligence through Simulated Evolution[M].New York：Wiley，1996.

［6］Holland J H.Adaptation in Natural and Artificial Systems[M].2nd ed.Cambridge.MA：MIT Press，1992.