南開大學計算機算法設計與分析

計算機算法設計與分析引子DonaldKnuth,算法學歷史上最卓越的計算機科學家之一,如此論述:受過良好訓練的計算機科學家知道怎樣處理算法:如何構造算法,操作算法,理解算法以及分析算法。這些知識遠不止為了編寫良好的計算機程序而準備的。算法是一種一般性的智能工具,它必定有助于我們對其他學科的理解,不管是化學,語言學,音樂,還是另外的科學。為什么算法會有這種作用呢?我們可以這樣理解:人們常說,一個人只有把知識教給別人，才能真正掌握它。實際上,一個人只有把知識教給“計算機”，才能“真正”掌握它，也就是說，將知識表述為一種算法……比起簡單地按照常規(guī)去理解事物，用算法將其形式化會使我們的理解更加深刻。Knuth,D.E.SelectedPapersonComputerScience,CSLIPublicationsandCambridgeUniversityPress,NewYork,1996有趣的問題1.西雅圖附近一家著名軟件公司主考官面試題：

4個人過橋，時間為晚上，只有一只手電筒，最多只能兩個人同時過橋，且必須帶手電，只能步行將手電簡帶來帶去，而不能扔來扔去。每個人走路的速度不同，甲過橋要１分鐘，乙過橋需要２分鐘，丙需要５分鐘，丁需要１０分鐘，兩個一起走，則速度等于其中較慢的人的速度。2.關于驗證一個數(shù)是否為素數(shù)的問題3.旅行商問題：如何走最短的路，經(jīng)過所有的城市。4.漢諾塔問題漢諾塔問題voidhanoi(intn,charone,chartwo,charthree)/*將n個盤子從one座借助two座，移到three座*/{if(n==1)move(one,three);else {hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); }}main(){intm;printf(inputthenumberofdiskes:);scanf(“%d”,&m);printf(“Thesteptomoving%3ddiskes:\n”,m);hanoi(m,’A’,’B’,’C’);}ABC每個盤子有三個位置,n個共有3n緒論

1.1 交通信號燈問題

1.2 什么是算法

1.3 算法的評價

1.4 基本概念

1.5 算法研究與Moore定律

1.6 MAXMIN的問題1.1交通信號燈問題1.1.1

問題

⑴每一車輛通過路口時都不會與其它車輛發(fā)生沖突； ⑵車輛在路口等待通過的時間盡可能少。1.1.2實例共有13條路線：ab,ac,adba,bc,bdda,db,dcea,eb,ec,ed1.1.3

圖著色問題

已知：n點無向圖G=<V,E>,||V||=n。求：G的最小色數(shù)(colornumber)k，使得用k種顏色對G的頂點著色，可令任二相鄰頂點著色不同。地圖著色問題，交通信號燈問題都可以歸結為圖的頂點著色問題無向圖頂點著色問題：頂點，邊最小色數(shù)k地圖著色問題：國家，相鄰關系最小色數(shù)k交通信號燈問題：路線，交叉關系最小相位（組）數(shù)k2.圖著色(GraphColoring）問題

圖著色問題是一個經(jīng)典的組合算法問題，源于地圖著色問題。在繪制地圖時，總是要求相鄰的國家著上不同的顏色以示區(qū)別。1852年一位英國大學生古德里（F.Guthrie）提出了一個猜測：為了給任一個平面地圖著色，并使任何有公共邊界的區(qū)域顏色不同，至多需要四種顏色。這就是四色問題，又稱四色猜想。古德里僅僅是提出了這個猜想，他和他的老師未能證明。2.圖著色(GraphColoring）問題

二十幾年后的1878年，著名數(shù)學家凱萊（A.Kayley）發(fā)表了一篇“論地圖著色”的文章，雖然仍沒有解決這個問題，卻掀起了四色猜想的研究熱。經(jīng)過一百年的探索，美國伊利諾大學的哈肯（W.Haken）與阿佩爾（K.Appel）通過改進算法，借助計算機（共用了1200個機時）終于在1976年完成了四色猜想的證明。當?shù)氐泥]局在寄出的信上除了通常的郵戳(postmark)外，還要加蓋“四色是足夠的”一句話以表示自豪。2.圖著色(GraphColoring）問題

當把地圖(Map)上的一個國家與圖(Graph)上的一個頂點對應，兩個國家的相鄰關系對應于無向圖上的邊，于是，上面關于地圖的“四色問題”實際上是無向圖的頂點著色問題的特例。無向圖的頂點著色問題是一個有名的NP完全問題，這類問題屬于“計算機難解”問題，關于著色問題算法的研究已有許多學者的大量成果。

Fig.1.2給出的無向圖對應于五叉路口實例，該圖有13個結點和20條邊，其中ba,dc,ed三個頂點是孤立點，說明這三條路線與其它所有路線不相交，就是所謂的“拐小彎”。

c1.1.4算法設計討論1.窮舉法令色數(shù)k從2開始，用k種顏色分別對13個頂點著色，共有k13種情形，當K＝5時，需要進行

20×(213+313+413+513)次比較。413=2262.剪枝法對窮舉法的改進。不必窮舉所有可能的著色法，例如：頂點ab著色為c1，則點ab的所有鄰點ea,da,bc,bd都不必著色為c1；…

第一個點，例如ab，可以只著一種顏色，因顏色的對稱性，ab取其它(k–1)種顏色的情形可不必再檢查。此剪枝法一項可以把計算量縮小到原來的1/k。3.啟發(fā)式(Heuristic)算法依賴于人的直覺知識：為了用最小色數(shù)為所有頂點著色，也就是要每一種顏色在不出現(xiàn)沖突的條件下為盡量多的頂點著色。算法1.1啟發(fā)式算法實現(xiàn)圖著色用k=1,2,3,…來表示顏色1#,2#,3#,…,Color[i]=3表示對i頂點著3#色，<i,j>∈E表示頂點i,j相鄰，Color[i]=0表示頂點i未著色此法又稱貪心法，比窮舉算法和剪枝算法快得多，當n不太小時，其計算量比前者要少千萬倍甚至更多，不過它不一定總是得到最優(yōu)解。例如Fig.1.3中的5點無向圖，用貪心法著色需要用紅(R)、黃(Y)、藍(B)三種顏色，但實際上，這不是該圖的最小色數(shù)，顯然，兩種顏色已可滿足要求。即：頂點1、3、4著紅色，頂點2、5著黃色。(不同編號順序)1.1.4討論1.權衡(trade-off)的概念窮舉法：思想最簡單、最直觀，但計算量最大。改進的窮舉法：比前者要快，容許的n值可以再大一些，不過對于大的n，計算量仍會很大，它比窮舉法有所改進的代價是程序較為復雜。啟發(fā)式的貪心算法：簡單，快速，但不能保證總是得到最優(yōu)解。2.最優(yōu)性(Optimality)GreedyColor算法是一種“近似最優(yōu)”算法。執(zhí)行的結果是，

k=4，13條路線分為4組：（括號里的路線為補充的不沖突項）ab,ac,ad,ba,dc,ed;bc,bd,ea,(ba,dc,ed);da,db,(ba,dc,ed,ad);eb,ec,(ba,dc,ed,ea).一般的說可能還有更好的分組方法，例如分為三組。不過，在這個實例中，卻不難證明分為4組已不能改進。這是因為從Fig.1.2中發(fā)現(xiàn)ac,bd,da,eb4個頂點組成一個完全子圖（又稱團，Clique），4點的無向完全圖至少需4色，因此這個解已不可改進。c3.算法設計討論·算法的研究與許多實際應用問題直接相關，它不僅是個理論問題；·一些典型的算法問題的研究，如著色問題、旅行商問題、背包問題等等，常常在應用算法的設計中發(fā)揮作用；·用來解一個問題，可以有多種不同的算法，它們的效果可能差別很大，如何設計有效的算法是算法理論的主要目標。1.2什么是算法1.2.1算法1.Webster辭典定義：算法即在有限步驟內解一個數(shù)學問題的過程，步驟中常常包括某一操作的重復。更廣義地說，一個算法就是為解一個問題或實現(xiàn)某一目標的逐步過程。2.D.E.Knuth定義：一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列；此外，它還應有五個重要特性：·有窮性：一個算法必須總是在執(zhí)行有窮步之后結束；·確定性：算法的每一步驟，必須是確切地定義的；·輸入：有0或多個輸入值；·輸出：有1或多個輸出值；·能行性：算法中要做的運算都是相當基本的，能夠精確地進行的。3.形式化定義：算法就是一個對任一有效輸入能夠停機的Turing機。1.2.2算法與問題

例：整數(shù)乘法問題全部可能輸入集合：{<a,b>|a,b∈Z}，其中Z表示整數(shù)集；一個實例：<2,4>,求：2×4=?旅行商問題(TravelingSalesmanProblem)實例集為：{n,Wn*n=[Wij]|n∈Z,Wij∈R,i,j∈[1,…,n]}；一個實例：n=4,該實例（n,W）就是求環(huán)游4個城市(1,2,3,4)且代價和最小的周游路線，其中權矩陣W給出了4個城市之間的距離（代價），Wij表示由城市i到城市j的距離（代價）。語言L<G,Σ>的識別問題其中G為文法，Σ為一字符集。L(G)為Σ上由G生成的語言，L(G)∈Σ*，Σ*表示由Σ中的字符組成的所有字符串集合。語言L的識別問題{G,Σ,ω|ω∈Σ*}的一個實例ω∈Σ*，識別算法判斷ω∈L(G)是否成立。算法研究對象：問題。問題由所有實例組成。一般對于問題P，總有其相應的實例集I，那么，一個算法A是問題P的算法，意味著把P的任一實例input∈I作為A的輸入，都能得到問題P的正確的輸出。一個問題可以有許多個不同的算法。1.2.3算法與程序程序(Program)可以用來描述算法，同一個算法可以用不同的語言編寫的程序來描述。程序不一定是算法。程序設計可以分為四個層次：算法、方法學、語言和工具。

抽象級更新速度算法程序設計方法程序設計語言編程工具1.3算法的評估1.3.1正確性算法的正確性是評估的前提。有些算法，特別是一些十分精致巧妙的算法，其正確性需要證明，有的證明難度較大，例如無向圖單源最短路徑問題的Dijkstra算法，構造最優(yōu)二分搜索樹的動態(tài)規(guī)劃算法的Knuth改進。有些算法，其正確性是明顯的，例如：算法1.2選擇排序算法SelectSort

1.3.2時間代價

評估算法的時間代價是算法分析的核心。算法的時間代價的大小用算法的時間復雜度(TimeComplexity)來度量。但要考慮到以下因素：

·用來運行算法的計算機的性能的差別；

·算法運行的軟件平臺和描述語言的差別；

·算法所解的問題是多種多樣的；

·同一問題的算法對不同的實例，所花的時間開銷也可能有很大的差別。1.3.3空間代價

空間消耗是衡量算法優(yōu)劣的另一重要因素。不過算法的空間復雜性分析的重要性常常列于時間復雜性分析之后。在許多應用問題中，人們往往以適當增加算法的空間代價來減少時間代價?？臻g復雜度的分析類似于時間復雜度的分析，其有關的概念和方法幾乎是平行的。1.3.4最優(yōu)性

一個算法不一定是最優(yōu)的。所謂最優(yōu)算法是指在某一種度量標準之下，優(yōu)于該問題的所有（可能的）算法。一般，某一問題的最優(yōu)算法是指在時間復雜度的計算基礎上的最優(yōu)性。算法1.3求n個不同整數(shù)中的最大元MaxElement對于任何n個整數(shù)，要求其最大元，至少需進行n-1次比較，因此，可以說上述算法Max(S)是最優(yōu)的。為了證明在n個不同元中求出最大元，至少需n-1次比較，可以把n個元劃分為三個動態(tài)的組A,B,C。

A：未知元的集合

B：已肯定不是最大元的元素集合

C：最大元的集合。

不難證明，任何一個通過二元比較求最大元的算法都是要從三個集合的元數(shù)為(n,0,0)（即|A|=n,|B|=0,|C|=0）狀態(tài)開始，經(jīng)過運行，最終達到(0,n-1,1)狀態(tài)，即：

這實際上是元素從集合A向B和C中移動的過程。但每次兩個元的比較至多只可把一個較小的元素從集合A移至集合B。因此，任何最大元算法至少要進行n-1次比較，從而證明了上述最大元算法Max(A)是最優(yōu)的。

ABCABC|A|=n|B|=0|C|=0|A|=n-1|B|=0|C|=1|A|=n-2|B|=1|C|=11.4算法理論的基本概念1.4.1基本操作算法的時間代價的度量不應依賴于算法運行的硬件和軟件平臺，因此不能從下面幾個方面來度量時間代價：

?算法運行的實際執(zhí)行時間；

?運行過程中所執(zhí)行的指令條數(shù)；(不同語言,不同編程風格)?運行過程中程序循環(huán)的次數(shù)。(循環(huán)體差別大)

因此需要引入基本操作的概念來度量時間代價。基本操作就是指算法運行中起主要作用且花費最多時間的操作。例如：兩個實數(shù)矩陣的乘法問題中，矩陣的實數(shù)元素之間的數(shù)乘是基本操作；對N個整數(shù)進行排序的算法中，整數(shù)間的比較是基本操作；移動操作；移動與比較。1.4.2問題實例長度

算法運行的時間（或空間）代價還與問題實例長度，即輸入規(guī)模有關，這稱為問題實例長度。

問題實例長度是指作為該問題的一個實例的輸入規(guī)模大小。例如：

排序問題：問題實例長度是待排序元素序列的長度n；

矩陣乘積：問題實例長度是矩陣（指n階方陣）的階數(shù)n；

圖的最短路徑問題：圖G=<V,E>的頂點數(shù)n=||V||和邊數(shù)m=||E||是問題實例長度；

字符串匹配問題：文本T的長度n，亦可再加上樣本P的長度m為問題實例長度。算法的時間（或空間）代價由該算法用于問題長度為n的實例所需要的基本操作次數(shù)來刻畫。一般一個算法的時間復雜度用函數(shù)T(n)(或T(n,m))表示，空間復雜度用S(n)表示。1.4.3復雜度的漸進性質算法的比較是根據(jù)復雜度函數(shù)的漸進性質的比較進行的。例如：算法A和算法B，其時間復雜度函數(shù)為TA(n)和TB(n)，在Fig.1.4中，雖然當n<n0時TB(n)<TA(n)，但在n>n0時，或說n充分大時(n->∞)，有TA(n)<TB(n)，因此認為算法A優(yōu)于算法B。㊣算法B有條件優(yōu)于算法A：在實際應用中問題規(guī)模是給定的1.4.4最壞情形和最好情形例：算法1.4插入排序算法Insertsortn=10時，有三種輸入：正序：123456789109次比較逆序：1098765432145次比較（9+1）9/2隨機：3745102961828次比較同一算法，相同的問題長度，不同的輸入，其時間代價一般不同。因此在實際的算法分析中，復雜度函數(shù)值T(n)不是唯一的，在大多數(shù)情況下取其最大值，即最壞情形的時間（空間）復雜度。設Dn為問題P的所有長度為n的實例集合，輸入實例I∈Dn

，||I||=n，而t(I)為用來解問題P的算法A在以I為輸入時的執(zhí)行代價（基本操作次數(shù)），則W(n)=MAX{t(I)}

I∈DnW(n)稱為算法A的最壞情形(WorstCase)時間復雜度。類似的，還可以定義最好情形（BestCase）時間復雜度，B(n)=MIN{t(I)}---最好與最壞復雜度有何用,何時用?

I∈Dn

平均復雜度何時用

1.4.5平均情形和算法的期望復雜度設算法A的輸入為I∈Dn的概率為P(I)，則

其中P(I)滿足為實例輸入I出現(xiàn)的概率，t(I)為算法A完成實例I的耗費值（即基本操作次數(shù)）。

期望復雜度比最壞情形復雜度更好的刻畫了算法的性能，但是，由于Dn一般很大，P(I)和t(I)較難計算，因此，平均情形的復雜度分析比較難。例如：在數(shù)組L[1,…,n]中搜索，求使L[j]=X的位置j。算法1.5順序搜索算法SeqSearch因為L[1,…,n]長度為n，不同的輸入實例由X的值決定，實例集Dn由下列實例組成：（1）X在L中，共有n種情況：I1,…,In

，Ii表示X=L[i] (i=1,…,n)；（2）X不在L中，這時X有許多可能值，把它們統(tǒng)記為In+1

。因為當X=L[k]時，t(Ik)=k，(k=1,…,n)，X不在L中時，t(In+1)=n。這時W(n)容易計算：W(n)=MAX{t(Ik)|k=1,2,…,n,n+1}=n。但計算A(n)則應首先設定I在Dn中的分布：設X在L中的概率為q，故X不在L中的概率為1-q，假定X在L中，它等于L的n個元素是等可能的，即P(Ik)=Pk=q/n,(k=1,…,n),P(In+1)=Pn+1=1-q，當q=1，即已知X在L中，A(n)=(n+1)/2，q=1/2，即X有一半可能在L中，A(n)=3n/4+1/4。也就是說，在上面的假設條件下，我們的順序搜索的平均代價大約是n/2次比較和3n/4次比較。1.4.6復雜度函數(shù)的表示

各種復雜度函數(shù)的表示方法大致可按表達的精確程度分為下面的三個等級:(何種情況下用相應的復雜度函數(shù))

1.解析表達式。用解析表達式刻畫復雜度函數(shù)是最精確的表達方式。例如·求n元中之最大元算法MaxElement的復雜度為T(n)=W(n)=A(n)=n–1?！ろ樞蛩阉魉惴ǖ淖顗那樾螘r間復雜度為W(n)=n；在指定分布條件及q=1情形下的期望時間復雜度為

A(n)=(n+1)/2。2.階（Order）表達式。為了簡化算法復雜度分析的方法，往往只需計算當問題規(guī)模較大時算法的漸進復雜度的階。定義1.1

稱（復雜度）函數(shù)T(n)是O(f(n))的，即

T(n)=O(f(n))，如果存在常數(shù)c>0與n0

，當n>n0時有T(n)≤cf(n)。例如：T1(n)=(n+1)/2=O(n),T2(n)=3n2+4n+5=O(n2)定義1.2

稱（復雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0

，當n>n0

時有T(n)≥cf(n)。例如：T1(n)=(n+1)/2=Ω(n),T2(n)=3n2+4n+5=Ω(n2)定義1.3

稱（復雜度）函數(shù)T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常數(shù)c1,c2>0與n0，當n>n0時有c1f(n)≥T(n)≥c2f(n)。例如：T1(n)=(n+1)/2=θ(n),T2(n)=3n2+4n+5=θ(n2)顯然，如果T(n)=O(f(n))且T(n)=Ω(f(n))，則T(n)=θ(f(n))。3.多項式函數(shù)和指數(shù)函數(shù)。多項式函數(shù)指T(n)為自變量n的多項式函數(shù)，例如T1(n)=n/2+1/2，T2(n)=3n2+4n+5等。而指數(shù)函數(shù)如T3(n)=2n+5，T4(n)=3n/2–8等等，自變量n出現(xiàn)在