算法的基本概念

第1章算法的基本概念

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

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

算法需要什么樣的資源，需要多少運(yùn)行時(shí)間、多少存儲(chǔ)空間，如何判定一個(gè)算法的好壞，在

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

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

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

1.1

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

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

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

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

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

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

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

1.1.1算法的定義和特征

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

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

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

算法1.1歐兒里德算法

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

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

inteuclid(intmzintn

intr;

do{

r=m%n

m=n;

算法設(shè)計(jì)與分析

8.}while(r)

9.returnm;

10.)

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

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

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

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

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

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

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

最大公因子。可以證明這個(gè)算法的正確性。

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

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

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

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

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

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

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

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

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

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

執(zhí)行。

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

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

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

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

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

最大公約數(shù)。

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

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

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

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

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

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

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

百億億計(jì)的運(yùn)算步驟，從理論上說，它是有限的，最終可以結(jié)束，但是，以當(dāng)代計(jì)算機(jī)每秒

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

算法。

?2?

第1章算法的基本概念

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

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

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

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

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

例1.1百雞問題。

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

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

各幾何？”意思是公雞每只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)

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

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

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

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

有組合進(jìn)行測試，凡是滿足上述3個(gè)約束方程的組合，都是問題的解。如果把問題轉(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)

于是，可用下面的算法來實(shí)現(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è)計(jì)與分析

15.

16.

17.

這個(gè)算法有三重循環(huán)，主要執(zhí)行時(shí)間取決于第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)次。當(dāng)〃=100時(shí)，內(nèi)循環(huán)的循環(huán)體執(zhí)行次數(shù)大于100萬次.

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

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

算法1.3改進(jìn)的百雞問題

輸入：所購買的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í)行時(shí)間取決于第8行開始的內(nèi)循環(huán)，其循環(huán)體的執(zhí)行次數(shù)

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

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

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

例L2貨郎擔(dān)問題。

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

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

市，而總路程最短。

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

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

?4?

第1章算法的基本概念

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

表示各個(gè)城市之間的距離，把這個(gè)矩陣稱為費(fèi)用矩陣。

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

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

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

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

算法1.4窮舉法版本的貨郎擔(dān)問題

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

輸出：旅行路線最小費(fèi)用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個(gè)城市的第i個(gè)排列于p;

8.cost=路線p的費(fèi)用；

9.if(cost<min){

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

11.min=cost;

12.)

13.i++;

14.)

15.)

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

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

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

時(shí)，運(yùn)行時(shí)間是3.62s,算法是可行的；當(dāng)〃=13時(shí)，運(yùn)行時(shí)間是1.72小時(shí)，還可以接受；當(dāng)

”=16時(shí)，運(yùn)行時(shí)間是242天，就不實(shí)用了；當(dāng)"=20時(shí)，運(yùn)行時(shí)間是7萬7千多年，這樣的

算法就不可取了。

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

nn\nnlnnlnn\

5120Hs9362ms131.72h1711,27year

6720Ps103.62s1424h18203year

75.04ms1139.9s1515day193857year

840.3ms12479.0s16242day2077146year

1.1.3算法的復(fù)雜性分析

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

?5?

算法設(shè)計(jì)與分析

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

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

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

多；更不會(huì)知道用窮舉法來解諸如貨郎擔(dān)一類的問題，甚至對(duì)一個(gè)不太大的”，都是不可行

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

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

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

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

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

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

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

析中，對(duì)時(shí)間復(fù)雜性的分析考慮得更多。

1.2算法的時(shí)間復(fù)雜性

在討論算法的時(shí)間復(fù)雜性時(shí)，要解決兩個(gè)問題：用什么來度量算法的復(fù)雜性？如何分析

和計(jì)算算法的復(fù)雜性？下面就來討論這兩個(gè)問題。

1.2.1算法的輸入規(guī)模和運(yùn)行時(shí)間的階

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

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

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

714gso當(dāng)〃的規(guī)模不大時(shí)，兩個(gè)算法運(yùn)行時(shí)間的差別不太明顯。

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

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

6.7s。當(dāng)"的規(guī)模變大時(shí)，兩個(gè)算法運(yùn)行時(shí)間的差別就很懸殊。

從匕面的分析以及對(duì)貨郎擔(dān)問題運(yùn)行時(shí)間的分析，可以看到下面兩點(diǎn)事實(shí)：第一，算法

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

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

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

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

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

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

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

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

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

?6,

第1章算法的基本概念

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

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

實(shí)時(shí)系統(tǒng)中，時(shí)間是非常關(guān)鍵的因素時(shí))。這是因?yàn)槿藗冊(cè)诜治鏊惴ǖ男阅?，或把兩個(gè)算法

的性能進(jìn)行比較時(shí)，對(duì)時(shí)間的估計(jì)是相對(duì)的，而不是絕對(duì)的。此外，對(duì)一個(gè)算法而言，人們

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

卜.述的運(yùn)算符“/”都表示整除操作。于是，百雞問題的第二個(gè)算法的時(shí)間花費(fèi)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)

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

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

C2

當(dāng)“很大時(shí)，J/C2的作用很小。為了對(duì)這兩個(gè)算法的效率進(jìn)行比較，基于上面的觀察，有

?7?

算法設(shè)計(jì)與分析

如下的定義：

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

lim"-7(?=0(1.1.11)

〃T8T(〃)

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

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

來衡量一個(gè)算法的時(shí)間復(fù)雜性。在上面的例子中，百雞問題的第一個(gè)算法的時(shí)間復(fù)雜性為

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

表1.2表示時(shí)間復(fù)雜性的階為log〃，“，〃log”當(dāng)〃=23,2、…，2脩時(shí)，算法

的漸近運(yùn)行時(shí)間。這里假定每一個(gè)操作是1ns。從表1.2中看到，當(dāng)階為2"、〃>64時(shí)，運(yùn)

行時(shí)間是以世紀(jì)衡量的。

另一方面，假定％,為…,是求解同一問題的6個(gè)算法，它們的時(shí)間復(fù)雜性分別為

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

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

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

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

規(guī)?？蓴U(kuò)大10倍，而算法4的求解規(guī)模只有微小增加，算法4基本不變。可見，時(shí)間復(fù)雜

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

乎其微的。

表1.3中，前四種算法的時(shí)間復(fù)雜性，與輸入規(guī)?！ǖ囊粋€(gè)確定的幕同階，計(jì)算機(jī)運(yùn)算

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

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

表1.2不同時(shí)間復(fù)雜性下不同輸入規(guī)模的運(yùn)行時(shí)間

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：小時(shí)：d：天：y：年：c：世紀(jì)。

?9?

算法設(shè)計(jì)與分析

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

算法

4A2A3A4A5

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

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

1.2.2運(yùn)行時(shí)間的上界，。記號(hào)

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

c2n\當(dāng)〃的規(guī)模增大時(shí)，常數(shù)。和C2對(duì)運(yùn)行時(shí)間的影響不大，此時(shí)，如果用。記號(hào)來表示

這兩個(gè)算法的運(yùn)行時(shí)間的上界，則可分別寫成。(/)和。(”2)。

在一般情況下，當(dāng)輸入規(guī)模大于或等于某個(gè)閾值"0時(shí)，算法運(yùn)行時(shí)間的上界是某個(gè)正常

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

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

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

多是。(g(〃))。

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

〃一>8

.l.im-----Koo

"f8g(")

即意味著：

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

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

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

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

21515

取沏=28,對(duì)V”Na。，有：

?,、/92161

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

21515

=13M2

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

2

T2(n)<cn=eg(")

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

像M那樣快。

這時(shí)，如果有一個(gè)新算法，其運(yùn)行時(shí)間的上界低于以往解同一問題的所有其他算法的上

界，就認(rèn)為建立了一個(gè)解該問題所需時(shí)間的新上界。

?10?

第1章算法的基本概念

1.2.3運(yùn)行時(shí)間的下界，Q記號(hào)

。記號(hào)表示算法運(yùn)行時(shí)間的上界，同樣，也可以用c記號(hào)來表示算法運(yùn)行時(shí)間的下界。

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

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

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

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

2

T2(n)>n=cg(")

這時(shí)，就認(rèn)為百雞問題的第二個(gè)算法的運(yùn)行時(shí)間是C("2)。它表明了這個(gè)算法的運(yùn)行時(shí)間的

下界。在一般情況下，當(dāng)輸入規(guī)模等于或大于某個(gè)閾值〃。時(shí)，算法運(yùn)行時(shí)間的下界是某一個(gè)

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

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

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

少是。(g(〃))。

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

.回#。

"T8g(〃)

即意味著：

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

這個(gè)記號(hào)表明一個(gè)算法的運(yùn)行時(shí)間增長至少像g5)那樣快。它被廣泛地用來表示解-

個(gè)特定問題的任何算法的時(shí)間下界。

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

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

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

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

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

1.2.4運(yùn)行時(shí)間的準(zhǔn)確界，?記號(hào)

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

何變化，該算法的運(yùn)行時(shí)間都界于"2和13M之間。這時(shí)，用記號(hào)?來表示這種情況，認(rèn)為

這個(gè)算法的運(yùn)行時(shí)間是。(〃2)。。記號(hào)表明算法的運(yùn)行時(shí)間有一個(gè)較準(zhǔn)確的界。

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

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

1?

算法設(shè)計(jì)與分析

號(hào)的定義如下：

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

存在自然數(shù)〃o和兩個(gè)正常數(shù)04cl4c2,使得對(duì)所有的"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ù)的。記號(hào)、C記號(hào)利0記號(hào)的例子：

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

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

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

所以，同樣：

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

所以，/(n)=Q(5(n))=Q(l),又因?yàn)椋?/p>

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

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

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

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

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

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

令"o=2,當(dāng)時(shí)，有：C2=6,g(n)="

f(n)<5n+n

=6n

=c2g(n)

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

同時(shí)，有：

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

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

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

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

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

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

2

令"o=2,當(dāng)時(shí)，有：c2=12,g(n)=n

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

?12?

第1章算法的基本概念

<12n2

=c2g(n)

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

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,當(dāng)時(shí)，有C1=5,g(〃)=2",使得：

n

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

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

令"o=4,當(dāng)時(shí)，有：c2=6,g(n)=2"

f(n)<5x2"+2"

<6x2n

=c2g(n)

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

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

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

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

因?yàn)椋?/p>

logn2=2logn

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

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

所以:logn2=0(logn)o

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

log#'=?(logn)

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

>1

因?yàn)椋?/p>

X,oS7-Xlogn

尸1j=i

=nlogn

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

?13?

算法設(shè)計(jì)與分析

>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,對(duì)所有的〃之沏,都有：

^logyS-nlogn

j=\4

=c2g(")

=Q(g("))

=Q(/?logn)

因此，有：

J=I

所以，

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

7=1

由此，可以證明：

log〃！=€)(〃logn)

1.2.5復(fù)雜性類型和。記號(hào)

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

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

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

則R是自反、對(duì)稱、傳遞的等價(jià)關(guān)系，它誘導(dǎo)的等價(jià)類，稱階是g(")的復(fù)雜性類型的等

價(jià)類。

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

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

?14?

第1章算法的基本概念

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

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

又因?yàn)椋?/p>

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

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

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

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

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

類似地，因?yàn)閘og2k=M>"log"，而log"!=@("log”)。所以,"!=。(2"一)，但

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

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

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

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

f(n)<cg(n)

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

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

8

"T8g(")

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

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

出下面的結(jié)論：

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

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

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

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

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

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

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

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

1.3算法的時(shí)間復(fù)雜性分析

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

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

的時(shí)間，并不表示該算法的實(shí)際執(zhí)行時(shí)間。因?yàn)檫@是在一種理想的計(jì)算模型下進(jìn)行統(tǒng)計(jì)的，

?15?

算法設(shè)計(jì)與分析

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

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

等操作數(shù)目。因?yàn)樵谶M(jìn)行這種統(tǒng)計(jì)時(shí)，忽略了編譯程序所產(chǎn)生的很多輔助操作，而這是無法

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

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

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

的時(shí)間統(tǒng)