徐素梅

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

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

1 時(shí)間復(fù)雜性

圖1

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

1.1 時(shí)間頻度

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

1.2 計(jì)算方法

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

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

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

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

O（1）

1.3 分類

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

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

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

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

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

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

圖2

變量計(jì)數(shù)：

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

2 空間復(fù)雜度

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

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

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

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

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

漸進(jìn)時(shí)間復(fù)雜度評價(jià)算法時(shí)間性能主要用算法時(shí)間復(fù)雜度的數(shù)量級（即算法的漸近時(shí)間復(fù)雜度）評價(jià)一個(gè)算法的時(shí)間性能

3 聯(lián)系

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

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

4 NPC問題

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

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

5 小結(jié)

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