徐素梅

（安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001）

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

1 時間復(fù)雜性

圖1

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

1.1 時間頻度

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

1.2 計算方法

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

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

b、算法的時間復(fù)雜度

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

例如：

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

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

O（1）

1.3 分類

按數(shù)量級遞增排列，常見的時間復(fù)雜度有：

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

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

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

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

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

圖2

變量計數(shù)：

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

2 空間復(fù)雜度

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

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

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

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

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

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

3 聯(lián)系

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

圖3 常用的算法的時間復(fù)雜度和空間復(fù)雜度

4 NPC問題

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

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

5 小結(jié)

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

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

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

［3］殷劍宏,吳開亞.[M]中國科學(xué)技術(shù)大學(xué)出版社，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.