算法的基本概念

第1章算法的基本概念

計算機系統(tǒng)中的任何軟件，都是由大大小小的各種軟件組成部分構(gòu)成，各自按照特定的

算法來實現(xiàn)，算法的好壞直接決定所實現(xiàn)軟件性能的優(yōu)劣。用什么方法來設(shè)計算法，所設(shè)計

算法需要什么樣的資源，需要多少運行時間、多少存儲空間，如何判定一個算法的好壞，在

實現(xiàn)一個軟件時，都是必須予以解決的。計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫

管理系統(tǒng)以及各種各樣的計算機應(yīng)用系統(tǒng)中的軟件，都必須用一個個具體的算法來實現(xiàn)。因

此，算法設(shè)計與分析是計算機科學與技術(shù)的一個核心問題。

1.1

在20世紀50年代，西方某些著名的詞典中，還未曾收錄過算法（Algorithm）一詞。根

據(jù)西方數(shù)學史家的考證，古代阿拉伯的一位學者寫了一部名著，名字為“Kitdbal-jabr

Wa'lmuqAbjla”（《復原和化簡的規(guī)貝lj》），作者的署名是AbU4AbdAllahMuhammadibnMusa

al-Khwarizml,從字面看，意思是“穆罕默德（Muhammad）的父親，摩西（Moses）的兒子，

KhwOrizm地方的人”。后來，這部著作流傳到了西方，結(jié)果，從作者署名中的aLKhw^rizml

派生出Algorithm（算法）一詞,而從作品名字中的al-jabr派生出Algebra（代數(shù)）一詞。隨

著時間的推移，Algorithm（算法）這個詞的含義，已經(jīng)完全與它原來的含義不同了。

1.1.1算法的定義和特征

歐幾里德曾在他的著作中描述過求兩個數(shù)的最大公因子的過程。20世紀50年代，歐幾

里德所描述的這個過程，被稱為歐幾里德算法，算法這個術(shù)語在學術(shù)上便具有了現(xiàn)在的含義。

下面是這個算法的例子及它的一種描述。

算法1.1歐兒里德算法

輸入：正整數(shù)m,n

輸出：m,n的最大公因子

inteuclid(intmzintn

intr;

do{

r=m%n

m=n;

算法設(shè)計與分析

8.}while(r)

9.returnm;

10.)

在此用一種類c語言來敘述最大公因子的求解過程。今后，在描述其他算法時，還可能

結(jié)合一些自然語言的描述，以代替某些繁瑣的具體細節(jié)，而更好地說明算法的整體框架。同

時，為了簡明地訪問二維數(shù)組元素，假定在函數(shù)調(diào)用時，二維數(shù)組可以作為參數(shù)傳遞，在函

數(shù)中可以動態(tài)地分配數(shù)組。讀者可以很容易地用其他方法來消除這些假定。

在算法的第5行，把,"除以〃的余數(shù)賦予r,第6行把〃的值賦予加，第7行把廠的值賦

予”，第8行判斷r是否為0,若非0,繼續(xù)轉(zhuǎn)到第5行進行處理；若為0,就轉(zhuǎn)到第9行處

理，第9行返回算法結(jié)束。按照上面這組規(guī)則，給定任意兩個正整數(shù)，總能返回它們的

最大公因子?？梢宰C明這個算法的正確性。

根據(jù)上面這個例子，可以給算法如下的定義：

定義1.1算法是解某一特定問題的一組有窮規(guī)則的集合。

算法設(shè)計的先驅(qū)者唐納德.E.克努特(DonaldE.Knuth)對算法的特征作了如下的描述：

(1)有限性。算法在執(zhí)行有限步之后必須終止。算法1」中，對輸入的任意正整數(shù)加、

n,在加除以"的余數(shù)賦予r之后，再通過r賦予“，從而使〃值變小。如此往復進行，最終

或者使，?為0,或者使〃遞減為1。這兩種情況，都最終使，?=0,而使算法終止。

(2)確定性。算法的每一個步驟，都有精確的定義。要執(zhí)行的每一個動作都是清晰的、

無歧義的。例如，在算法1」的第5行中，如果加、〃是無理數(shù)，那么，機除以"的余數(shù)是

什么，就沒有一個明確的界定。確定性的準則意味著必須確保在執(zhí)行第5行時，，"和”的值

都是正整數(shù)。算法1.1中規(guī)定了加、"都是正整數(shù)，從而保證了后續(xù)各個步驟中都能確定地

執(zhí)行。

(3)輸入。一個算法有0個或多個輸入，它是由外部提供的，作為算法開始執(zhí)行前的

初始值，或初始狀態(tài)。算法的輸入是從特定的對象集合中抽取的。算法1.1中有兩個輸入，"、

n,就是從正整數(shù)集合中抽取的。

(4)輸出。一個算法有一個或多個輸出，這些輸出與輸入有特定的關(guān)系，實際上是輸

入的某種函數(shù)。不同取值的輸入，產(chǎn)生不同結(jié)果的輸出。算法1.1中的輸出是輸入〃的

最大公約數(shù)。

(5)能行性。算法的能行性指的是算法中有待實現(xiàn)的運算，都是基本的運算。原則上

可以由人們用紙和筆，在有限的時間里精確地完成。算法1.1用一個正整數(shù)來除另一個正整

數(shù)，判斷一個整數(shù)是否為0以及整數(shù)賦值等，這些運算都是能行的。因為整數(shù)可以用有限的

方式表示，而且，至少存在一種方法來完成一個整數(shù)除以另一個整數(shù)的運算。如果所涉及的

數(shù)值必須山展開成無窮小數(shù)的實數(shù)來精確地完成，則這些運算就不是能行的了。

必須注意到，在實際應(yīng)用中，有限性的限制是不夠的。一個實用的算法，不僅要求步驟

有限，同時要求運行這些步驟所花費的時間是人們可以接受的。如果一個算法需要執(zhí)行數(shù)十

百億億計的運算步驟，從理論上說，它是有限的，最終可以結(jié)束，但是，以當代計算機每秒

數(shù)億次的運算速度，也必須運行數(shù)百年以上時間，這是人們所無法接受的，因而是不實用的

算法。

?2?

第1章算法的基本概念

算法設(shè)計的整個過程，可以包含對問題需求的說明、數(shù)學模型的擬制、算法的詳細設(shè)計、

算法的正確性驗證、算法的實現(xiàn)、算法分析、程序測試和文檔資料的編制。本書所關(guān)心的是

串行算法的設(shè)計與分析，其他相關(guān)的內(nèi)容以及并行算法，可參考專門的書籍。這里，只在涉

及有關(guān)內(nèi)容時，才對相應(yīng)的內(nèi)容進行論述。

1.1.2算法設(shè)計的例子，窮舉法

例1.1百雞問題。

公元5世紀末，我國古代數(shù)學家張丘建在他所撰寫的《算經(jīng)》中，提出了這樣的一個問

題：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛

各幾何？”意思是公雞每只5元、母雞每只3元、小雞3只1元，用100元錢買100只雞，

求公雞、母雞、小雞的只數(shù)。

令。為公雞只數(shù)，b為母雞只數(shù)，c為小雞只數(shù)。根據(jù)題意，可列出下面的約束方程：

a+b+c=100(1.1.1)

5a+3h+c/3=100(1.1.2)

c%3=0(1.1.3)

其中，運算符“/”為整除運算，“％”為求模運算，式(1.1.3)表示c被3除余數(shù)為0。

這類問題用解析法求解有困難，但可用窮舉法來求解。窮舉法就是從有限集合中，逐一

列舉集合的所有元素，對每一個元素逐一判斷和處理，從而找出問題的解。

上述百雞問題中，a、b、c的可能取值范圍為0700,對在此范圍內(nèi)的“、h、c的所

有組合進行測試，凡是滿足上述3個約束方程的組合，都是問題的解。如果把問題轉(zhuǎn)化為用

"元錢買"只雞，w為任意正整數(shù)，則式(1.1.1),式(1.1.2)變?yōu)椋?/p>

a+h+c=n(1.1.4)

5a+3h+c/3=n(1.1.5)

于是，可用下面的算法來實現(xiàn)：

算法1.2百雞問題

輸入：所購買的3種雞的總數(shù)目n

輸出：滿足問題的解的數(shù)IRk,公雞，母雞，小雞的只數(shù)g[],m[]zs[]

1.voidchicken_question(intn,int&k,intg[],intm[],ints[])

2.{

3.inta,b,c;

4.k=0;

5.for(a=0;a<=n;a++){

6.for(b=0;b<=n;b++){

7.for(c=0;c<=n;C++){

8.if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){

9.g(k]=a;

10.m[k]=b;

11.s[k]=c;

12.k++;

13.)

?3?

算法設(shè)計與分析

15.

16.

17.

這個算法有三重循環(huán)，主要執(zhí)行時間取決于第7行開始的內(nèi)循環(huán)的循環(huán)體的執(zhí)行次數(shù)。

外循環(huán)的循環(huán)體執(zhí)行〃+1次，中間循環(huán)的循環(huán)體執(zhí)行(〃+1)(〃+1)次，內(nèi)循環(huán)的循環(huán)體執(zhí)行

(〃+1)(〃+1)(〃+1)次。當〃=100時，內(nèi)循環(huán)的循環(huán)體執(zhí)行次數(shù)大于100萬次.

考慮到"元錢只能買到〃/5只公雞，或〃/3只母雞。因此，有些組合可以不必考慮。而

小雞的只數(shù)又與公雞及母雞的只數(shù)相關(guān)，上述的內(nèi)循環(huán)可以省去。這樣，算法1.2可以改為：

算法1.3改進的百雞問題

輸入：所購買的3種雞的總數(shù)目n

輸出：滿足問題的解的數(shù)目k,公雞，母雞，小雞的只數(shù)

1.voidchicken_problem(intn,int&k,intg[]zintm[]zints[])

2.{

3.inti,j,a,b,c;

4.k=0;

5?i=n/5;

6.j=n/3;

7.for(a=0;a<=i;a++){

8.(b=0;b<=j;b++){

9.c=n-a-b;

10.if((5*a+3*b+c/3==n)&&(c%3==0))

11.g[k]

12.m[k]

13.s[k]

14.k++;

15.

16.

17.

18.

算法1.3有兩重循環(huán)，主要執(zhí)行時間取決于第8行開始的內(nèi)循環(huán)，其循環(huán)體的執(zhí)行次數(shù)

是(〃/5+1)(〃/3+1)。當”=100時，內(nèi)循環(huán)的循環(huán)體的執(zhí)行次數(shù)為21x34=714次，這和算

法1.2的100萬次比較起來，僅是原來的萬分之七，有重大的改進。

對某類特定問題，在規(guī)模較小的情況下，窮舉法往往是一個簡單有效的方法。

例L2貨郎擔問題。

貨郎報問題是一個經(jīng)典問題。某售貨員要到若干個城市銷售貨物，已知各城市之間的距

離，要求售貨員選擇出發(fā)的城市及旅行路線，使每一個城市僅經(jīng)過一次，最后回到原出發(fā)城

市，而總路程最短。

如果對任意數(shù)目的"個城市，分別用1?"的數(shù)字編號，則這個問題歸結(jié)為在有向賦權(quán)圖

G=<K,E>中，尋找一條路徑最短的哈密爾頓回路問題。其中，K={1,2,…何，表示城市頂

?4?

第1章算法的基本概念

點，邊(i,j)eE表示城市i到城市)的距離，，,_/=1,2,…”。這樣，可以用圖的鄰接矩陣C來

表示各個城市之間的距離，把這個矩陣稱為費用矩陣。

售貨員的每一條路線，對應(yīng)于城市編號1,2…〃的一個排列。用一個數(shù)組來存放這個排列

中的數(shù)據(jù)，數(shù)組中的元素依次存放旅行路線中的城市編號?！皞€城市共有”!個排列，于是，

售貨員共有"!條路線可供選擇。采用窮舉法逐一計算每一條路線的費用，從中找出費用最小

的路線，便可求出問題的解。下面是用窮舉法解這個問題的算法。

算法1.4窮舉法版本的貨郎擔問題

輸入：城市個數(shù)n,費用矩陣CU[]

輸出：旅行路線最小費用min

1.voidsalesman_problem(intn,float&min,intt[],floatc[][])

2.(

3.intp[n],i=1;

4.floatcost;

54min=MAX_FLOAT_NUM;

6.while(i<=n!){

7.產(chǎn)生n個城市的第i個排列于p;

8.cost=路線p的費用；

9.if(cost<min){

10.把數(shù)組p的內(nèi)容復制到數(shù)組t;

11.min=cost;

12.)

13.i++;

14.)

15.)

這個算法的執(zhí)行時間取決于第6行開始的while循環(huán)，它產(chǎn)生一個路線的城市排列，并

計算該路線所需要的時間。這個循環(huán)的循環(huán)體共需執(zhí)行”!次。假定每執(zhí)行一次，需要時

間，則整個算法的執(zhí)行時間隨"的增長而增長的情況，如表L1所示。從表中看到，當”=10

時，運行時間是3.62s,算法是可行的；當〃=13時，運行時間是1.72小時，還可以接受；當

”=16時，運行時間是242天，就不實用了；當"=20時，運行時間是7萬7千多年，這樣的

算法就不可取了。

表1.1算法1.4的執(zhí)行時間隨”的增長而增長的情況

nn\nnlnnlnn\

5120Hs9362ms131.72h1711,27year

6720Ps103.62s1424h18203year

75.04ms1139.9s1515day193857year

840.3ms12479.0s16242day2077146year

1.1.3算法的復雜性分析

上面的第一個例子，說明了改進算法的設(shè)計方法對提高算法性能的重要性。第二個例子,

?5?

算法設(shè)計與分析

說明了對一個不太大的“，采用窮舉法來解諸如貨郎擔一類的問題，都是行不通的?？梢圆?/p>

用哪些算法設(shè)計方法，來有效地解決現(xiàn)實生活中的問題，就是本書所要敘述的一個問題。但

是，如果不是通過上面的簡單分析，就不知道改進版的百雞問題算法比原來的算法效率高很

多；更不會知道用窮舉法來解諸如貨郎擔一類的問題，甚至對一個不太大的”，都是不可行

的。把這個問題再引申一下，對所設(shè)計的算法，如何說明它是有效的；或者，如果有兩個解

同樣問題的算法，如何知道這?個算法比那?個算法更有效？這就提出了另一個問題，如何

分析算法的效率，這是本書所要敘述的另一個問題。

一般來說，可以用算法的復雜性來衡量一個算法的效率。對所設(shè)計的算法，普遍關(guān)心的

是算法的執(zhí)行時間和算法所需要的存儲空間。因此，也把算法的復雜性，劃分為算法的時間

復雜性和算法的空間復雜性。算法的時間復雜性越高，算法的執(zhí)行時間越長；反之，執(zhí)行時

間越短。算法的空間復雜性越高，算法所需的存儲空間越多；反之越少。在算法的復雜性分

析中，對時間復雜性的分析考慮得更多。

1.2算法的時間復雜性

在討論算法的時間復雜性時，要解決兩個問題：用什么來度量算法的復雜性？如何分析

和計算算法的復雜性？下面就來討論這兩個問題。

1.2.1算法的輸入規(guī)模和運行時間的階

假定百雞問題的第一個算法，其最內(nèi)部的循環(huán)體每執(zhí)行一次，需時間。當”=100時,

第一個算法的這個循環(huán)體共需執(zhí)行100萬次，約需執(zhí)行1s時間。第二個算法最內(nèi)部的循環(huán)體

每執(zhí)行一次，也需1RS時間。當“=100時，第二個算法的這個循環(huán)體共需執(zhí)行714次，約需

714gso當〃的規(guī)模不大時，兩個算法運行時間的差別不太明顯。

如果把〃的大小改為10000,即10000元買10000只雞，以同樣的計算機速度執(zhí)行第一

個算法，約需11天零13小時；而用第二種算法，則需(10000/5+1)(10000/3+1).,約為

6.7s。當"的規(guī)模變大時，兩個算法運行時間的差別就很懸殊。

從匕面的分析以及對貨郎擔問題運行時間的分析，可以看到下面兩點事實：第一，算法

的執(zhí)行時間隨問題規(guī)模的增大而增長，增長的速度隨不同的算法而不同。當問題規(guī)模較小時,

不同增長速度的兩個算法，其執(zhí)行時間的差別或許并不明顯。而當規(guī)模較大時，這種差別則

非常大，甚至令人不能接受。第二，沒有一個方法能準確地計算算法的具體執(zhí)行時間。這一

事實是基于如下原因的：算法的執(zhí)行時間，不但取決于算法是怎樣實現(xiàn)的，也取決于算法是

用什么語言編寫的，用什么編譯系統(tǒng)實現(xiàn)的，編譯系統(tǒng)所生成代碼的質(zhì)量如何，在什么樣的

計算機上執(zhí)行的，而不同計算機的性能、速度都不相同，致使在同一臺計算機上執(zhí)行，加法

指令和乘法指令的執(zhí)行時間差別就很大。人們無法對所有這些都作出準確的統(tǒng)計，致使不能

對某臺特定計算機的執(zhí)行性能作出準確的統(tǒng)計，由于軟件規(guī)模很大，結(jié)構(gòu)復雜，運行狀態(tài)變

化很大。每一種運行狀態(tài)都有各種各樣的條件判斷，依據(jù)條件判斷而確定是否需要執(zhí)行的各

?6,

第1章算法的基本概念

種操作，其執(zhí)行時間也難以控制。

實際上，在評估一個算法的性能時，并不需對算法的執(zhí)行時間作出準確的統(tǒng)計(除非在

實時系統(tǒng)中，時間是非常關(guān)鍵的因素時)。這是因為人們在分析算法的性能，或把兩個算法

的性能進行比較時，對時間的估計是相對的，而不是絕對的。此外，對一個算法而言，人們

不僅希望算法與實現(xiàn)它的語言無關(guān)、與執(zhí)行它的計算機無關(guān)，同時也希望時算法運行時間的

測量，能適應(yīng)技術(shù)的進步。而且，人們所關(guān)心的并不是較小的輸入規(guī)模，而是在很大的輸入

實例下算法的性能。也即是：算法的運行時間，隨著輸入規(guī)模的增長而增長的情況。

于是，可以假定算法是在這樣的計算模型下運行的：所有的操作數(shù)都具有相同的固定字

長；所有操作的時間花費都是一個常數(shù)時間間隔。把這樣的操作，稱為一個初等操作。例如，

下面就是一些初等操作：算術(shù)運算；比較和邏輯運算；賦值運算等。

這樣，如果輸入規(guī)模為〃，百雞問題的第一個算法的時間花費可估計如下：第4行需執(zhí)

行1個操作；第5行需執(zhí)行1+25+1)個操作；第6行需執(zhí)行“+1+2(n+1)2個操作；第7

行需執(zhí)行5+1)2+25+1)3個操作;第8行需執(zhí)行145+1)3個操作;第9、10、11、12行循

環(huán)一次各執(zhí)行一個操作，執(zhí)行與否取決于第8行的條件語句。所以，這四行的執(zhí)行時間，不

會超過4(”+1)3。于是，百雞問題的第一個算法的時間花費((〃)可估算如下：

2233

7'1(n)<l+2(M+l)+n+l+2(M+l)+(n+l)+16(n+l)+4(n+l)

=20〃3+63M+69〃+27(1.1.6)

當〃增大時，例如當“=100萬時，算法的執(zhí)行時間主要取決于式(1.1.6)的第一項，而第二、

三、四項對執(zhí)行時間的影響，只有它的幾十萬分之一，可以忽略不計。這時，第一項的常數(shù)

20,隨著”的增大，對算法的執(zhí)行時間也變得不重要。于是，可把豈(〃)寫為：

T1*(")=sC]"3Cj>0(1.1.7)

這時，稱T「(")的階是同樣，對百雞問題的第二個算法，也可進行如下估計：第4行執(zhí)

行1個操作；第5、6行各執(zhí)行2個操作；第7行執(zhí)行1+25/5+1)個操作；第8行執(zhí)行

〃/5+1+2(〃/5+1)("/3+1)個操作；第9行執(zhí)行3(n/5+1)("/3+1)個操作;第10行執(zhí)行

10(n/5+l)(〃/3+l)個操作：第11、12、13、14行循環(huán)一次各執(zhí)行一個操作，執(zhí)行與否取

決于第10行的條件語句。所以，這四行的執(zhí)行時間，不會超過4(w/5+l)(w/3+l)個操作。

卜.述的運算符“/”都表示整除操作。于是，百雞問題的第二個算法的時間花費72(〃)可估算

如下：

7'2(n)<l+2+2+l+2(n/5+l)+n/5+l+2(n/5+l)(n/3+l)+

(3+10+4)(/?/5+l)(n/3+l)

19161.。、

=—n2~+〃+28(1.1.8)

1515

同樣，隨著”的增大，72(〃)也可寫為：

T,*(")=sc2Mc2>0(1.1.9)

這時，稱72"(")的階是M。把T1*(")和72*(")進行比較，有：

T,*(n)/7'2*(n)=—n(1.1.10)

C2

當“很大時，J/C2的作用很小。為了對這兩個算法的效率進行比較，基于上面的觀察，有

?7?

算法設(shè)計與分析

如下的定義：

定義1.2設(shè)算法的執(zhí)行時間為7(〃)，如果存在T*(〃)，使得：

lim"-7(?=0(1.1.11)

〃T8T(〃)

就稱7*(〃)為算法的漸近時間復雜性。

在算法分析中，往往對算法的時間復雜性和算法的漸近時間復雜性不加區(qū)分，并用后者

來衡量一個算法的時間復雜性。在上面的例子中，百雞問題的第一個算法的時間復雜性為

7」(〃)，它的階是〃3;第二個算法的時間復雜性為72*(〃)，它的階是"2。

表1.2表示時間復雜性的階為log〃，“，〃log”當〃=23,2、…，2脩時，算法

的漸近運行時間。這里假定每一個操作是1ns。從表1.2中看到，當階為2"、〃>64時，運

行時間是以世紀衡量的。

另一方面，假定％,為…,是求解同一問題的6個算法，它們的時間復雜性分別為

n,〃k)g〃,〃2,〃3,2",〃!，并假定在計算機和C2上運行這些算法，機的速度是C|機的10

倍。若這些算法在G機上運行時間為了，可處理的輸入規(guī)模是"|，在C2機上運行同樣時間，

可處理的輸入規(guī)?？蓴U大為"2,則表1.3表示對不同時間復雜性的算法，計算機速度提高后

可處理的規(guī)模"2和的關(guān)系。從表L3中看到，當計算機速度提高10倍后，算法4的求解

規(guī)?？蓴U大10倍，而算法4的求解規(guī)模只有微小增加，算法4基本不變?？梢?，時間復雜

性為2"或〃!這類的算法，用提高計算機的運算速度來擴大它們的求解規(guī)模，其可能性是微

乎其微的。

表1.3中，前四種算法的時間復雜性，與輸入規(guī)?！ǖ囊粋€確定的幕同階，計算機運算

速度的提高，可使解題規(guī)模以一個常數(shù)因子的倍數(shù)增加。習慣上把這類算法稱為多項式時間

算法，而把后兩種算法稱為指數(shù)時間算法。這兩類算法，在效率上有本質(zhì)區(qū)別。

表1.2不同時間復雜性下不同輸入規(guī)模的運行時間

nlog/?nnlognJ2M

83ns8ns24ns64ns512ns256ns

164ns16ns64ns256ns4.096gs65.536/s

325ns32ns160ns1.024ps32.768RS4294.967ms

646ns64ns384ns4.096ps262.144ps5.85c

1287ns128ns896ns16.384ps1997.15211s1020c

2568ns256ns2.04即s65.536RS16.777ms1058c

5129ns512ns4.608ps262.1442134.218ms10l35c

102410ns1.024^is10.24gs1048.576RS1073.742ms10289c

20481Ins2.048gs22.52即s4194.304"8589.935ms10598c

409612ns4.09611s49.152RS16.777ms68.719s10⑵4c

44

819213ns8.196/s106.54即s67.174ms549.752s1027c

1638414ns16.384RS229.376ps268.435ms1.222h10咖3c

3276815ns32.768ps49L52RS1073.742ms9.773h109M5c

6553616ns65.536ps1048.576。4294.967ms78.187h10,9Wc

?8?

第1章算法的基本概念

說明：ns：納秒：ps：微秒；ms：亳秒：s：秒；h：小時：d：天：y：年：c：世紀。

?9?

算法設(shè)計與分析

表1.3計算機速度提高后，不同算法復雜性求解規(guī)模的擴大情況

算法

4A2A3A4A5

時間復雜性nnlognM2nnl

n2和?1的關(guān)系10n|8.38〃]3.16〃]2.15?i721+3.3川

1.2.2運行時間的上界，。記號

百雞問題的第一種算法和第二種算法，它們所執(zhí)行的初等操作數(shù)，分別至多為3和

c2n\當〃的規(guī)模增大時，常數(shù)。和C2對運行時間的影響不大，此時，如果用。記號來表示

這兩個算法的運行時間的上界，則可分別寫成。(/)和。(”2)。

在一般情況下，當輸入規(guī)模大于或等于某個閾值"0時，算法運行時間的上界是某個正常

數(shù)的g(“)倍，就稱算法的運行時間至多是。(g(〃))。。記號的定義如下：

定義1.3令N為自然數(shù)集合，R+為正實數(shù)集合。函數(shù)/：N-R+,函數(shù)g：N-R+，若

存在自然數(shù)"0和正常數(shù)c，使得對所有的都有〃")4cg("),就稱函數(shù)/(〃)的階至

多是。(g(〃))。

因此，如果存在lim/(〃)/g(〃)，則：

〃一>8

.l.im-----Koo

"f8g(")

即意味著：

/(")=。(8(及))

這個定義表明：/(〃)的增長最多像g(〃)的增長那樣快。這時稱。(8(〃))是/(〃)的上界。

例如，對百雞問題的第二個算法，由式(1.1.8)有：

T(n)<—n2+—n+28

21515

取沏=28,對V”Na。，有：

?,、/92161

T-,(n)<——n+——n+n

21515

=13M2

令C=13,并令g(")=M,有：

2

T2(n)<cn=eg(")

所以，T2(〃)=O(g(〃))=O("2)。這說明，百雞問題的第二個算法，其運行時間的增長最多

像M那樣快。

這時，如果有一個新算法，其運行時間的上界低于以往解同一問題的所有其他算法的上

界，就認為建立了一個解該問題所需時間的新上界。

?10?

第1章算法的基本概念

1.2.3運行時間的下界，Q記號

。記號表示算法運行時間的上界，同樣，也可以用c記號來表示算法運行時間的下界。

仍以百雞問題的第二個算法為例，第11、12、13、14行，僅在條件成立時才執(zhí)行，其執(zhí)行

次數(shù)未知。假定條件都不成立，這些語句??次也沒有執(zhí)行，該算法的執(zhí)行時間至少為：

7'2(?)>l+2+2+l+2(n/5+l)+n/5+l+2(n/5+l)(?/3+1)+(3+10)(n/5+l)(n/3+l)

243..

=n+—"+24

5

>n2

2

當取"o=l時，Vn>n0,存在常數(shù)c=l,g(n)=n,使得：

2

T2(n)>n=cg(")

這時，就認為百雞問題的第二個算法的運行時間是C("2)。它表明了這個算法的運行時間的

下界。在一般情況下，當輸入規(guī)模等于或大于某個閾值〃。時，算法運行時間的下界是某一個

正常數(shù)的g(")倍，就稱算法的運行時間至少是。(g(，?))。。記號的定義如下：

定義1.4令N為自然數(shù)集合，R+為正實數(shù)集合。函數(shù)N-R+,函數(shù)g：N-R+,若

存在自然數(shù)"0和正常數(shù)小使得對所有的〃2，％，都有/(")wcg(")，就稱函數(shù)"”)的階至

少是。(g(〃))。

因此，如果存在“l(fā)Ti8m/(〃)/g(〃)，則：

.回#。

"T8g(〃)

即意味著：

y(")=c(g(〃))

這個記號表明一個算法的運行時間增長至少像g5)那樣快。它被廣泛地用來表示解-

個特定問題的任何算法的時間下界。

例如，在聯(lián)個大小不同、順序零亂的數(shù)據(jù)中，尋找??個最小的數(shù)據(jù)，至少需要”-1次比

較操作，因此，它的階是0(〃)。以后還將說明：基于比較的排序算法，它的階是O(〃k>g〃)，

這也表明：再也不能設(shè)計出一個基于比較的排序算法，其運行時間的階能夠低于。("log")。

由。記號和C記號的定義，可得到下面的結(jié)論：

結(jié)論1.1/(")的階是C(g(")),當且僅當g(〃)的階是0(/(〃))。

1.2.4運行時間的準確界，?記號

百雞問題的第二個算法，運行時間的上界是13〃2,下界是”2,這表明不管輸入規(guī)模如

何變化，該算法的運行時間都界于"2和13M之間。這時，用記號?來表示這種情況，認為

這個算法的運行時間是。(〃2)。。記號表明算法的運行時間有一個較準確的界。

在一般情況下，如果輸入規(guī)模等于或大于某個閾值“0,算法的運行時間以qg(")為其

下界，以c2g(〃)為其上界，其中，0<Cj<C2y就認為該算法的運行時間是。(g(〃))。。記

1?

算法設(shè)計與分析

號的定義如下：

定義1.5令N為自然數(shù)集合，R+為正實數(shù)集合。函數(shù)f：N-R+，函數(shù)g：N-R+，若

存在自然數(shù)〃o和兩個正常數(shù)04cl4c2,使得對所有的"2“°,都有：

c}g(n)<f(n)<c2g(n)

就稱函數(shù)/(“)的階是@(g(")).

因此，如果存在lim/(")/g(")，則：

〃一>8

..小)

hm------c

isg(n)

即意味著：

/(n)=0(g(M))

其中，c是大于0的常數(shù)。

下面是一些函數(shù)的。記號、C記號利0記號的例子：

例1.3常函數(shù)/(〃)=4096。

令"o=O,c=4096,使得對g(〃)=l,對所有的〃有：

f(n)<4096x1=eg(〃)

所以，同樣：

/(H)>4096x1=eg(〃)

所以，/(n)=Q(5(n))=Q(l),又因為：

cg(n)<f(n)<cg(n)

所以，/(n)=0(l)?

例1.4線性函數(shù)/(")=5"+2。

令"o=O,當w2"o時，有J=5,g(")=”，使得：

f(n)>5n=ctg(n)

所以，/(n)=。(8(〃))=。(〃)。

令"o=2,當時，有：C2=6,g(n)="

f(n)<5n+n

=6n

=c2g(n)

所以，f(”)=O(g("))=O(n)。

同時，有：

Cig(n)<f(n)<c2g(n)

所以，/(zi)=0(n)o

例1.5平方函數(shù)/(〃)=8,/+3〃+2。

令"0=0,當ZIN"。時，有C]=8,g(")="2,使得：

/(n)>8n2=￡]?(?)

所以，〃")=C(g(n))=C(M)。

2

令"o=2,當時，有：c2=12,g(n)=n

/(>2)<8?2+3n+n

?12?

第1章算法的基本概念

<12n2

=c2g(n)

所以，“")=0(g("))=0("2)。同時，有：

Cig(n)<f(n)<c2g(n)

所以，/(n)=0(n2),

通過上面的例子，可得出下面的結(jié)論：

結(jié)論1.2令：

kk

f(n)=akn+ak_tn^'+—Fatn+a0ak>0

則有：/(〃)=。(#),且/(〃)=C("?),因此，有：/(”)=€)(/)。

例1.6指數(shù)函數(shù)f5)=5X2"+M。

令"o=O,當時，有C1=5,g(〃)=2",使得：

n

/(n)>5x2=cxg(n)

所以，/")=C(g"))=Q(2")。

令"o=4,當時，有：c2=6,g(n)=2"

f(n)<5x2"+2"

<6x2n

=c2g(n)

所以，/(“)=O(g(“))=O(2")。同時，有：

clg(n')<f(n)<c2g(n)

所以，/(n)=0(2")o

例1.7對數(shù)函數(shù)/(")=logM。

因為：

logn2=2logn

令"o=l,q=1,c2=3,g(〃)=log",有：

qg(")421og"4c2g(")

所以:logn2=0(logn)o

例1.7表明，在一般情況下，對任何正常數(shù)都有：

log#'=?(logn)

例1.8函數(shù)/(〃)=，log/

>1

因為：

X,oS7-Xlogn

尸1j=i

=nlogn

令〃0=1,q=l,g(n)=wlog/I,有：

?13?

算法設(shè)計與分析

>og

j=i

所以，

Zlog/=。(g(〃))=。(〃logk)

J=1

另一方面，假定”是偶數(shù)，

J.儀

^logj>221ogy

n.n

=-log—

22

=^(logn-l)

=—(logn+log/T-2)

4

因止匕，令，%=4,c2=1/4,g(n)=nlogn,對所有的〃之沏,都有：

^logyS-nlogn

j=\4

=c2g(")

=Q(g("))

=Q(/?logn)

因此，有：

J=I

所以，

^logJ=0(^(M))=0(/?logH)

7=1

由此，可以證明：

log〃！=€)(〃logn)

1.2.5復雜性類型和。記號

不同的函數(shù)具有不同的復雜性，因此，可對復雜性進行分類。

定義1.6令R是函數(shù)集合尸上的一個關(guān)系，RqFxF,有

R={<f，g>"eFAgeFA/(")=O(g("))}

則R是自反、對稱、傳遞的等價關(guān)系，它誘導的等價類，稱階是g(")的復雜性類型的等

價類。

因此，所有常函數(shù)的復雜性類型都是。(1);所有線性函數(shù)的復雜性類型都是。(〃)；所

有的2階多項式函數(shù)的復雜性類型都是。(〃2),如此等等。

?14?

第1章算法的基本概念

令函數(shù)”〃)=4096,函數(shù)g(〃)=3〃+2,則存在〃o=l,c=1365,使得對所有的〃之〃°,

有/1(〃)《eg(〃)。因此。(〃)=O(g(〃))=。(〃)。

又因為：

〃->8g(〃)"->83〃+2

因此，"〃)#c(g(")),貝IJ：/(〃)聲。(g(〃))。所以：/(")=4096和g(〃)=3〃+2是屬

于不同復雜性類型的函數(shù)。

因為log"!=?(〃log"),且log2"=〃。由此可以推出：2"=O(n\),而”!4。(2"),因

此，2"和〃!是屬于不同復雜性類型的函數(shù)。

類似地，因為log2k=M>"log"，而log"!=@("log”)。所以,"!=。(2"一)，但

2/W。(加)。所以，這兩個函數(shù)也是屬于不同復雜性類型的函數(shù)。

為了表示兩個函數(shù)具有不同類型的復雜性，可使用如下定義的。記號：

定義1.7令N為自然數(shù)集合，R+為正實數(shù)集合。函數(shù)/：N-R+，函數(shù)g：N-R+,若

存在自然數(shù)"o和正常數(shù)c,使得對所有的"Na。，都有

f(n)<cg(n)

就稱函數(shù)/(〃)是o(g("))。

由此，如果存在lim/(“)/g("),則

8

"T8g(")

即意味著/(n)=o(g(n))

這個定義表明，隨著"趨于非常大，/(〃)相對于g(〃)變得不重要。由這個定義可以推

出下面的結(jié)論：

結(jié)論1.3/(M)=o(g(n))當且僅當f(")=O(g(“))而g(w)wO(/(“))°

例如：nlog?=o(n2),等價于"log"=。("2),而“2#o(”iog〃)。同樣，2"=o(n!),

等價于2"=。(〃!)，而加二0(2")。

可以用偏序關(guān)系/(〃)Yg")來表示/(〃)=o(g(〃))，例如，nlogn-<n2?在算法分析

中，經(jīng)常遇到如下一些類型的復雜性，它們的階分別是：1、loglog"、log"、G、、〃、

nlog"、"?、2"、"！、2"

如果用“Y”來表示它們之間的復雜性關(guān)系，就可以組成如下的一個體系結(jié)構(gòu)：

1YloglognYlog"YYY〃Y"log"YY2"Y〃!Y2/

1.3算法的時間復雜性分析

在分析百雞問題的兩個算法時，都必須統(tǒng)計算法每一行所需執(zhí)行的初等操作數(shù)目，從而

得到算法所需執(zhí)行的全部初等操作數(shù)目，以此來代表算法的執(zhí)行時間。顯然，這樣統(tǒng)計出來

的時間，并不表示該算法的實際執(zhí)行時間。因為這是在一種理想的計算模型下進行統(tǒng)計的，

?15?

算法設(shè)計與分析

即所有的操作數(shù)都具有相同大小的字長，所有數(shù)據(jù)的存取時間都一樣，所有操作都花費相同

的時間間隔。此外，用這種方法統(tǒng)計出來的結(jié)果，也并不表示它就是算法所需執(zhí)行的全部初

等操作數(shù)目。因為在進行這種統(tǒng)計時，忽略了編譯程序所產(chǎn)生的很多輔助操作，而這是無法

準確統(tǒng)計的；止匕外，算法在運行時，很多操作是在運行過程中才判斷是否需要執(zhí)行的，因此

這些操作的數(shù)目是難于預(yù)料的。實際上，要準確地統(tǒng)計一個算法所需執(zhí)行的全部初等操作數(shù)

目是非常麻煩的，甚至是不可能的。前面的分析也說明，一般并不預(yù)期得到算法的一個準確

的時間統(tǒng)