《算法設計與分析-C++語言描述（第4版）》全套教學課件

算法設計與分析

——C++語言描述DeSignandAnalysisofAlgorithmsInC++

全套可編輯PPT課件

課程簡介課程名稱：算法設計與分析

DesignandAnalysisofAlgorithms先修課程：面向對象程序設計語言C++，數(shù)據(jù)結構

第1部分算法和算法分析

第1章算法問題求解基礎

1.1算法概述1.2問題求解方法

1.3算法設計與分析

1.4遞歸和歸納

1.1算法概述

1.1.1什么是算法

算法（algorithm）一個算法是對特定問題求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列5個特征:

輸入（input）：算法有零個或多個輸入量；輸出（output）：算法至少產(chǎn)生一個輸出量；確定性（definiteness）：算法的每一條指令都有確切的定義，沒有二義性；能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)；有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。

歐幾里德算法(輾轉相除法)計算兩個整數(shù)m和n（0≤m＜n)的最大公約數(shù)，記為gcd(m,n)。

【程序1-1】

歐幾里德遞歸算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}

【程序1-1】

歐幾里德遞歸算法intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}

【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}

【程序1-3】Gcd的連續(xù)整數(shù)檢測算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; intt=m>n?n:m; while(m%t||n%t)t--; returnt;}1.1.2為什么學習算法

算法是計算機科學的基礎，更是程序的基石，只有具有良好的算法基礎才能成為訓練有素的軟件人才。對于計算機專業(yè)的學生來說，學習算法的理由是非常充分的。因為你必須知道來自不同計算領域的重要算法，你也必須學會設計新的算法、確認其正確性并分析其效率。隨著計算機應用的日益普及，各個應用領域的研究和技術人員都在使用計算機求解他們各自專業(yè)領域的問題，他們需要設計算法，編寫程序，開發(fā)應用軟件，所以學習算法對于越來越多的人來說變得十分必要。

1.2問題求解方法

1.2.1問題和問題求解問題求解（problemsolving）是尋找一種方法來實現(xiàn)目標。問題求解過程（problemsolvingprocess）是人們通過使用問題領域知識來理解和定義問題，并憑借自身的經(jīng)驗和知識去選擇和使用適當?shù)膯栴}求解策略、技術和工具，將一個問題描述轉換成問題解的過程。計算機求解問題的關鍵之一是尋找一種問題求解策略（problemsolvingstrategy），得到求解問題的算法，從而得到問題的解。

1.2.2問題求解過程

理解問題（understandtheproblem）

設計方案（deviseaplan）

實現(xiàn)方案（carryouttheplan）

回顧復查（lookback）

1.2.3系統(tǒng)生命周期

一個計算機程序的開發(fā)過程就是使用計算機求解問題的過程。軟件工程（softwareengineering）將軟件開發(fā)和維護過程分成若干階段，稱為系統(tǒng)生命周期（systemlifecycle）或軟件生命周期。

軟件生命周期劃分為:分析（analysis）設計（design）編碼（codingorprogramming）測試（testing）維護（maintenance）等5個階段。前4個階段屬于開發(fā)期，最后一個階段處于運行期。

1.3算法設計與分析

1.3.1算法問題求解過程

算法分類一個精確算法（exactalgorithm）總能保證求得問題的解。一個啟發(fā)式算法（heuristicalgorithm）通過使用某種規(guī)則、簡化或智能猜測來減少問題求解時間。

對于最優(yōu)化問題，一個算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximationalgorithm）。如果在算法中需做出某些隨機選擇，則稱為隨機算法（randomizedalgorithm）。1.3.2如何設計算法

使用計算機的問題求解策略主要指算法設計策略（algorithmdesignstrategy）。

1.3.3如何表示算法

算法描述方法自然語言流程圖偽代碼程序設計語言本書使用C/C++語言描述算法

1.3.4如何確認算法確認一個算法是否正確的活動稱為算法確認（algorithmvalidation）使用數(shù)學方法證明算法的正確性，稱為算法證明（algorithmproof）。程序測試（programtesting）是指對程序模塊或程序總體，輸入事先準備好的樣本數(shù)據(jù)（稱為測試用例，testcase），檢查該程序的輸出，來發(fā)現(xiàn)程序存在的錯誤及判定程序是否滿足其設計要求的一項積極活動。

1.3.5如何分析算法算法分析（algorithmanalysis）活動是指對算法的執(zhí)行時間和所需空間的估算。當然在算法寫成程序后，便可使用樣本數(shù)據(jù)，實際測量一個程序所消耗的時間和空間，這稱為程序的性能測量（performancemeasurement）。

1.4遞歸和歸納

1.4.1遞歸

遞歸定義遞歸（recursive）定義是一種直接或間接引用自身的定義方法。一個合法的遞歸定義包括兩部分：基礎情況（basecase）和遞歸部分。例1-1

斐波那契數(shù)列

例1-1

斐波那契數(shù)列

遞歸算法當一個算法采用遞歸方式定義時便成為遞歸算法。一個遞歸算法是指直接或間接調用自身的算法。

【程序1-4】

求FnlongFib(longn){ if(n<=1)returnn; elsereturnFib(n-2)+Fib(n-1);}

可以用所謂的遞歸樹（recursivetree）來描述程序1-4的函數(shù)Fib執(zhí)行時的調用關系。

圖1-2計算Fib（4）的遞歸樹

遞歸數(shù)據(jù)結構使用遞歸方式定義的數(shù)據(jù)結構稱為遞歸數(shù)據(jù)結構（recursivedatastructure）。

1.4.2遞歸算法示例

例1-2

逆序輸出正整數(shù)的各位數(shù)

【程序1-5】

voidPrintDigit(unsignedintn){ cout<<n%10; //輸出最后一位數(shù)dk if(n>=10)PrintDigit(n/10); //以逆序輸出前k-1位數(shù)}

例1-3漢諾塔問題（towerofHanoi）假定有三個塔座：X，Y，Z，在塔座X上有n個直徑大小各不相同，按圓盤大小從小到大編號為1，2，…，n的圓盤。現(xiàn)要求將X塔座上n個圓盤移到塔座Y上，并仍按同樣順序疊排。圓盤移動時必須遵循下列規(guī)則：（1）每次只能移動一個圓盤；（2）圓盤可以加到塔座X，Y，Z中任意一個上；（3）任何時刻都不能將一個較大的圓盤放在較小的圓盤之上。

【程序1-6】

漢諾塔問題enumtower{A='X',B='Y',C='Z'};voidMove(intn,towerx,towery){//將第n個圓盤從塔座x移到塔座y的頂部

cout<<"Thedisk"<<n<<"ismovedfrom" <<char(x)<<"totopoftower"<<char(y)<<endl;}

voidHanoi(intn,towerx,towery,towerz){//將x上部的n個圓盤移到y(tǒng)上，順序不變。

if(n){ Hanoi(n-1,x,z,y); Move(n,x,y); Hanoi(n-1,z,y,x); }}1.4.3歸納證明定理1-1對于n≥0，程序1-5是正確的。

證明：（歸納法證明）當n是1位數(shù)時，程序顯然是正確的。假定函數(shù)PrintDigit對所有位數(shù)小于k（k＞1）的正整數(shù)都能正確運行，當n的位數(shù)為k位時，此時有n≥10，算法必定先執(zhí)行語句cout<<n%10;然后執(zhí)行語句if(n>

10)PrintDigit(n/10);。

由于

n/10

是n的前k-1位數(shù)字形成的數(shù)，歸納法假設函數(shù)調用PrintDigit(n/10)能夠將它正確地（并在有限步內）按數(shù)字的逆序輸出，那么，現(xiàn)在先執(zhí)行語句輸出個位數(shù)字（n%10），然后由于按逆序輸出前k-1位數(shù)字的做法是能夠正確按逆序輸出全部k位數(shù)字的，所以程序1-5是正確的。算法設計與分析

——C++語言描述DeSignandAnalysisofAlgorithmsInC++

第2章算法分析基礎

2.1算法復雜度2.2漸近表示法

2.3遞推關系2.4分攤分析2.1算法復雜度

2.1.1什么是好的算法

好的算法一個好的算法應具有以下4個重要特性:正確性（correctness）：算法的執(zhí)行結果應當滿足預先規(guī)定的功能和性能要求。簡明性（simplicity）：算法應思路清晰、層次分明、容易理解、利于編碼和調試。效率（efficiency）：算法應有效使用存儲空間，并具有高的時間效率。最優(yōu)性（optimality）：算法的執(zhí)行時間已達到求解該類問題所需時間的下界。

程序健壯性是指當輸入不合法數(shù)據(jù)時，程序應能做適當處理而不至于引起嚴重后果。其含義是：當程序萬一遇到意外時，能按某種預定方式做出適當處理。正確性和健壯性是相互補充的。

2.1.2影響程序運行時間的因素影響程序運行時間的因素主要有：程序所依賴的算法；問題規(guī)模和輸入數(shù)據(jù)；計算機系統(tǒng)性能。

2.1.3算法的時間復雜度

抽象機模型設抽象機提供由m個基本運算（也可稱為語句）組成的運算集O={O1,O2,…,Om}，每個運算都是基本的，它們的執(zhí)行時間是有限常量。同時設執(zhí)行第i個運算Oi所需的時間是

i，1≤i≤m。

時間復雜度一個算法的時間復雜度（timecomplexity）是指算法運行所需的時間。設有一個在抽象機上運行的算法A，I是某次運行時的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運行時間T是n和I的函數(shù)，記做T(n,I)。又設在該次運算中抽象機的第i個基本運算Oi的執(zhí)行次數(shù)為

i，1≤i≤m，

i也是n和I的函數(shù)，記做

i(n,I)。那么，算法A在輸入為I時的運行時間是：

設有一個在抽象機上運行的算法A，I是某次運行時的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運行時間T是n和I的函數(shù)，記做T(n,I)。又設在該次運算中抽象機的第i個基本運算Oi的執(zhí)行次數(shù)為

i，1≤i≤m，

i也是n和I的函數(shù)，記做

i(n,I)。那么，算法A在輸入為I時的運行時間是：最好、最壞和平均時間復雜度最好時間復雜度最壞時間復雜度平均時間復雜度

2.1.4使用程序步分析算法

一個程序步（programstep）是指在語法上或語義上有意義的程序段，該程序段的執(zhí)行時間必須與問題實例的規(guī)模無關。例子

【程序2-1】

求數(shù)組元素累加之和的迭代程序floatSum(floatlist[],constintn){floattempsum=0.0;count++;//針對賦值語句

for(inti=0;i<n;i++){count++; //針對for循環(huán)語句

tempsum+=list[i];count++; //針對賦值語句

}count++;//針對for的最后一次執(zhí)行

count++; //針對return語句

returntempsum;}

設RSum（list,n）的程序步為T(n)

T(n)=2+T(n-1)=2+2+T(n-2)=2*3+T(n-3)

=2*n+T(0)=2*n+2

【程序2-2】求數(shù)組元素累加之和的遞歸程序floatRSum(floatlist[],constintn){count++;//針對if條件

if(n){count++;//針對RSum調用和return語句

returnRSum(list,n-1)+list[n-1];}count++; //針對return語句

return0;}

【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}2.1.5算法的空間復雜度

一個算法的空間復雜度（spacecomplexity）是指算法運行所需的存儲空間。程序運行所需的存儲空間包括以下兩部分：固定空間需求（fixedspacerequirement）這部分空間與所處理數(shù)據(jù)的大小和個數(shù)無關，也就是說，與問題實例的特征無關?？勺兛臻g需求（variablespacerequirement）這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關。

2.2漸近表示法

2.2.1大O記號定義2-1

設函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在兩個正常數(shù)c和n0，使得當n≥n0時，有f(n)≤cg(n)，則記做f(n)=O(g(n))，稱為大O記號（bigOhnotation）。

例2-1f(n)=2n+3=O(n)當n≥3時，2n+3≤3n，所以，可選c=3，n0=3。對于n≥n0，f(n)=2n+3≤3n，所以，f(n)=O(n)，即2n+3

O(n)。這意味著，當n≥3時，程序2-1的程序步不會超過3n，2n+3=O(n)。

例2-2

f(n)=10n2+4n+2=O(n2)對于n≥2時，有10n2+4n+2≤10n2+5n，并且當n≥5時，5n≤n2，因此，可選c=11,n0=5；對于n≥n0，f(n)=10n2+4n+2≤11n2，所以f(n)=O(n2)。

例2-3

f(n)=n！=O(nn)對于n≥1，有n(n

1)(n

2)…1≤nn，因此，可選c=1，n0=1。對于n≥n0，f(n)=n！≤nn，所以，f(n)=O(nn)。

例2-3

10n2+9

O(n)使用反證法，假定存在c和n0，使得對于n≥n0，10n2+9≤cn始終成立，那么有10n+9/n≤c，即n≤c/10

9/(10n)總成立。但此不等式不可能總成立，取n=c/10+1時，該不等式便不再成立。定理2-1

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項式，且am＞0，則f(n)=O(nm)。證明：取n0=1，當n≥n0時，有

f(n)=amnm+am

1nm

1+

+a1n+a0

|am|nm+|am

1|nm

1+

+|a1|n+|a0|

(|am|+|am

1|/n+

+|a1|/nm

1+|a0|/nm)nm

(|am|+|am

1|+

+|a1|+|a0|)nm可取c=|am|+|am

1|+

+|a1|+|a0|，定理得證。

漸近時間復雜度使用大O記號及下面定義的幾種漸近表示法表示的算法時間復雜度，稱為算法的漸近時間復雜度（asymptoticcomplexity）。只要適當選擇關鍵操作，算法的漸近時間復雜度可以由關鍵操作的執(zhí)行次數(shù)之和來計算。一般地，關鍵操作的執(zhí)行次數(shù)與問題的規(guī)模有關，是n的函數(shù)。

【程序2-3】

矩陣乘法for（i=0;i<n;i++）//n+1for（j=0;j<n;j++）{//n(n+1)c[i][j]=0;//n2for（k=0;k<n;k++）//n2(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}

2.2.2

記號定義2-2

設有函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在兩個正常數(shù)

c和n0，使得當n≥n0時，有f(n)≥c

g(n)，則記做f(n)=

(g(n))，稱為

記號（omeganotation）。

例2-5f(n)=2n+3=

(n)對所有n，2n+3≥2n，可選c=2，n0=0。對于n≥n0，f(n)=2n+3≥2n，所以，f(n)=

(n)，即2n+3

(n)。

例2-6f(n)=10n2+4n+2=

(n2)對所有n，10n2+4n+2≥10n2，可選c=10，n0=0。對于n≥n0，f(n)=10n2+4n+2≥10n2，所以，f(n)=

(n2)。

定理2-3

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項式，且am＞0，則f(n)=

(nm)。2.2.3

記號定義2-3設有函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當n≥n0時，有c1g(n)≤f(n)≤c2

g(n)，則記做f(n)=

(g(n))，稱為

記號（Thetanotation）。

例2-7f(n)=2n+3=

(n)，即2n+3

(n)。例2-8f(n)=10n2+4n+2=

(n2)。定理2-4

如果f(n)=amnm+am

1nm

1+…+a1n+a0是m次多項式，且am＞0，則f(n)=

(nm)。2.2.4小o記號定義2-4f(n)=o(g(n))當且僅當f(n)=O(g(n))且f(n)

(g(n))例2-9

f(n)=2n+3=o(n2)，即2n+3

o(n2)。

2.2.5算法按時間復雜度分類算法按計算時間分類凡漸近時間復雜度有多項式時間限界的算法稱做多項式時間算法（polynomialtimealgorithm），而漸近時間復雜度為指數(shù)函數(shù)限界的算法稱做指數(shù)時間算法（exponentialtimealgorithm）。

最常見的多項式時間算法的漸近時間復雜度O(1)＜O(logn)＜O(n)＜O(nlog

n)＜O(n2)＜O(n3)最常見的指數(shù)時間算法的漸近時間復雜度O(2n)＜O(n！)＜O(nn)

2.3遞推關系

2.3.1遞推方程遞推方程（recurrenceequation）是自然數(shù)上一個函數(shù)T(n)，它使用一個或多個小于n時的值的等式或不等式來描述。遞推方程也稱為遞推關系或遞推式。遞推方程必須有一個初始條件（也稱邊界條件）。

例2-10程序1-5的時間分析設n=d1d2

dk是k位數(shù)，當k=1時，只執(zhí)行cout語句和if判定語句；當n至少是2位數(shù)（k＞1）時，除了執(zhí)行這兩個操作外，還需執(zhí)行遞歸函數(shù)調用PrintDigit(n/10)，

n/10

是k

1位數(shù)。

T(k)=2k+2=

(k)2.3.2替換方法替換方法要求首先猜測遞推式的解，然后用歸納法證明。例2-11

使用替換方法分析程序1-6。可以先對以下這些小的示例進行計算：T(3)=7=23

1；T(4)=15=24

1；T(5)=31=25

1；T(6)=63=26

1看起來，似乎T(n)=2n

1，n≥1。

證明：（歸納法證明）當n=1時，T(1)=1，結論成立。歸納法假設：當k＜n時，有T(k)=2k

1，那么，當k=n時，T(n)=2T(n

1)+1=2(2n

1

1)+1=2n

1。因此，對所有n≥1，T(n)=2n

1=

(2n)。2.3.3迭代方法迭代方法的思想是擴展遞推式，將遞推式先轉換成一個和式，然后計算該和式，得到漸近復雜度。例2-12

使用迭代方法分析程序1-6。函數(shù)Hanoi中兩次調用自身，函數(shù)調用使用的實在參數(shù)均為n

1，函數(shù)Move所需時間具有常數(shù)界

(1)，可以將其視為一個程序步，于是有：

擴展并計算此遞推式：T(n)=2T(n

1)+1=2(2T(n

2)+1)+1=22T(n

2)+2+1=23T(n

3)+22+2+1

=2n

1T(1)+…+22+2+1=2n

1+…+22+2+1=2n

1

使用遞歸樹（recursiontree）可以形象地看到遞推式的迭代過程。

例2-13

T(n)=2T(n/2)+n的遞歸樹

例2-14T(n)=T(n/3)+T(2n/3)+n的遞歸樹

2.3.4主方法

主方法在遞歸算法分析中，常需要求解如下形式的遞推式：T(n)=aT(n/b)+f(n)式中，a≥1和b＞1是常數(shù)，f(n)是一個漸近正函數(shù)，n/b指

n/b

或

n/b

。求解這類遞推式的方法稱為主方法。

定理2-5

（主定理）設a≥1和b＞1為常數(shù)，f(n)是一個函數(shù)，T(n)由下面的遞推式定義T(n)=aT(n/b)+f(n)式中，n/b指

n/b

或

n/b

，則T(n)有如下的漸近界：（1）若對某常數(shù)

＞0，有f(n)=O()，則T(n)=

()；（2）若f(n)=

()，則T(n)=

(logn)；（3）若對某常數(shù)

＞0，有f(n)=

()，且對某個常數(shù)c＜1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=

(f(n))。

例2-15T(n)=16T(n/4)+n因為a=16,b=4,=n2,f(n)=n=O()=O(n2

)，其中，

=1與主定理的情況（1）相符合，T(n)=

()=

(n2)。例2-16T(n)=T(3n/7)+1因為a=1,b=7/3,==n0=1,f(n)=1=

()，所以，符合主定理情況（2），T(n)=

(logn)=

(logn)。例2-17T(n)=3T(n/4)+nlogn因為a=3,b=4,==O(n0.793),f(n)=nlogn=

，其中，

≈0.2。由于對足夠大的n，3(n/4)log(n/4)≤(3/4)nlogn，這里c=3/4，符合主定理情況（3）。T(n)=

(f(n))=

(nlogn)。

例2-18T(n)=2T(n/2)+nlogn由于a=2,b=2,f(n)=nlogn和=n。看起來似乎屬于主定理情況（3），但事實上不是。因為f(n)只是漸近大于n，但并不是多項式大于n。f(n)與的比值是logn，對于任何正數(shù)

，logn漸近小于n

，所以，此例不能運用主定理。

算法設計與分析

——C++語言描述DeSignandAnalysisofAlgorithmsInC++

第2部分算法設計策略

第5章分治法

5.1

分治法的基本思想5.2

求最大最小元 5.3

二分搜索5.4

排序問題5.5選擇問題5.6斯特拉森矩陣乘法

5.1一般方法

5.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個問題能夠用分治法求解的要素是：第一，問題能夠按照某種方式分解成若干個規(guī)模較小、相互獨立且與原問題類型相同的子問題；第二，子問題足夠小時可以直接求解；第三，能夠將子問題的解組合成原問題的解。由于分治法要求分解成同類子問題，并允許不斷分解，使問題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問題，因此，分治法求解很自然導致一個遞歸算法。

【程序5-1】

分治法SolutionTypeDandC(ProblemTypeP){ ProblemTypeP1，P2，

，Pk; if(Small(P))returnS(P); else{ Divide(P，P1，P2，

，Pk); ReturnCombine(DandC(P1)，

DandC(P2)，…，DandC(Pk)); }}

【程序5-2】

一分為二的分治法SolutionTypeDandC(intleft，intright){ if(Small(left,right))returnS(left,right); else{ intm=Divide(left，right); ReturnCombine(DandC(left，m)，

DandC(m+1，right)); }}5.1.2算法分析

采用分治法求解問題通常得到一個遞歸算法。如果較大的問題被分解成同樣大小的幾部分，那么分析相應算法的執(zhí)行時間，往往可得到如下的遞推關系式：T(n)=aT(n/b)+cnk，T(1)=c

定理5-1設a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

設r=bk/a，下面分三種情況計算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以

5.1.3

數(shù)據(jù)結構【程序5－3】可排序表類template<classK,classD>structE{//可排序表中元素的類型

operatorK()const{returnkey;}Kkey;Ddata;};

template<classT>classSortableList{//可排序表類public:SortableList(intmSize);~SortableList();

private:

T*l;intmaxSize;intn;};

5.2求最大最小元

問題在一個元素集合中尋找最大元素和最小元素的問題。5.2.1

分治法求解

【程序5－4】求最大最小元template<classT>voidSortableList<T>::MaxMin(T&max,T&min)const{ if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }}

【程序5－5】分治法求最大最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{ Tmin1,max1; if(i==j)max=min=l[i];elseif(i==j-1) if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; }

else{ intm=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; if(min>min1)min=min1; }}

5.2.2時間分析定理5－2

設有n個元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。

5.3二分搜索

問題在有序表（已按關鍵字值非減排序）中搜索給定元素的問題。5.3.1

分治法求解

intSortableList<T>::BSearch(constT&x,intleft,intright)const后置條件:

在范圍為[left,right]的表中搜索與x有相同關鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗?！境绦?－6】二分搜索算法框架template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{ if(left<=right){intm=Divide(left+right);if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right); elsereturnm;}return-1;}

5.3.2

對半搜索

對半搜索對半搜索是一種二分搜索。設當前搜索的子表為（aleft,aleft+1,…,aright），令

m=(left+right)/2

【程序5－7】對半搜索遞歸算法template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(left+right)/2;if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}定理5－3對于n

0，程序5－7的對半搜索遞歸函數(shù)BSearch是正確的。

5.3.3

二叉判定樹

二分搜索過程的算法行為可以用一棵二叉樹來描述。通常稱這棵描述搜索算法執(zhí)行過程的二叉樹為二叉判定樹(binarydecisiontree)。

性質5－1

具有n個內結點的對半搜索二叉判定樹的左子樹上有

(n-1)/2

個內結點，右子樹上有

n/2

個內結點。

性質5－2

具有n(n>0）個內結點的二叉判定樹的高度為

logn

+1

（不計外結點）。

性質5－3

若n=2h-1，則對半搜索二叉判定樹是滿二叉樹。

性質5－4

若n=2h-1，則對半搜索二叉判定樹的外結點均在h+1層上，否則，在第h或h+1層上，h=

logn

+1。

定理5－4

對半搜索算法在成功搜索的情況下，關鍵字值之間的比較次數(shù)不超過

logn

+1。對于不成功的搜索，算法需要作

logn

或

logn

+1次比較。定理5－5

對半搜索算法在搜索成功時的平均時間復雜度為

(logn)。

5.3.4搜索算法的時間下界

定理5－6

在一個有n個元素的集合中，通過關鍵字值之間的比較，搜索指定關鍵字值的元素，任意這樣的算法在最壞情況下至少需要作

log

n

+1次比較。

5.4排序問題

問題排序是將一個元素序列調整為按指定關鍵字值的遞增（或遞減）次序排列的有序序列。

5.4.1

合并排序

合并兩個有序序列

兩路合并排序的基本運算是把兩個有序序列合并成一個有序序列。

【程序5－9】Merge函數(shù)template<classT>voidSortableList<T>::Merge(intleft,intmid,intright){ T*temp=newT[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++];}

分治法求解將待排序的元素序列一分為二分，得到兩個長度基本相等的子序列，如同對半搜索的做法；然后對兩個子序列分別排序，如果子序列較長，還可繼續(xù)細分，直到子序列的長度不超過1為止；當分解所得的子序列已排列有序，可以采用上面介紹的將兩個有序子序列，合并成一個有序子序列的方法，實現(xiàn)將子問題的解組合成原問題解，這是分治法不可缺少的一步。

【程序5－10】兩路合并排序template<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}

template<classT>voidSortableList<T>::MergeSort(){ MergeSort(0,n-1);}

性能分析合并排序遞歸算法的時間復雜度為O(nlog

n)。

5.4.2

快速排序快速排序采用一種特殊的分劃操作對排序問題進行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K

為主元。經(jīng)過一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個子序列。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都不小于主元。

分劃操作

【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：left

right inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j); Swap(left,j); returnj;}快速排序算法

【程序5－12】快速排序template<classT>voidSortableList<T>::QuickSort(){QuickSort(0,n-1);}template<classT>voidSortableList<T>::QuickSort(intleft,intright){ if(left<right){intj=Partition(left,right);QuickSort(left,j-1); QuickSort(j+1,right); }}

時間分析最壞情況時間

W(n)

W(n-1)+n+1

W(n-2)+(n+1)+n

W(1)+(n+1)+

+3=O(n2)

平均情況時間

5.4.3排序算法的時間下界定理5－7

任何一個通過關鍵字值比較對n個元素進行排序的算法，在最壞情況下，至少需作（n/4）log

n次比較。

5.5選擇問題

問題選擇問題（selectproblem）是指在n個元素的集合中，選出某個元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問題(kth-smallest)。

5.5.1

分治法求解

設原表長度為n，假定經(jīng)過一趟分劃，分成兩個左右子表，其中左子表是主元及其左邊元素的子表，設其長度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是第k小元素；否則若k<p，第k小元素必定在左子表中，需求解的子問題成為在左子表中求第k小元素；若k>p，則第k小元素必定在右子表中，需求解的子問題成為在右子表中求第k-p小元素。

5.5.2

隨機選擇主元

隨機選主元算法

假定表中元素各不相同，并且隨機選擇主元，即在下標區(qū)間[left,right]中隨機選擇一個下標r，以該下標處的元素為主元。

【程序5－13】Select函數(shù)template<classT>ResultCodeSortableList<T>::Select1(T&x,intk){if(n<=0||k>n||k<=0)returnOutOfBounds;intleft=0,right=n;l[n]=INFTY;do{ intj=rand()%(right-left+1)+left; Swap(left,j); j=Partition(left,right); if(k==j+1){x=l[j];returnSuccess;} elseif(k<j+1)right=j; elseleft=j+1; }while(true);}

定理5－8

程序5－13的Select算法的平均時間A(n)=O(n)。算法的最壞情況時間復雜度O(n2)。5.5.3

線性時間選擇算法改進的選擇算法采用二次取中法(medianofmediansrule)確定主元

【程序5－14】線性時間選擇算法ResultCodeSortableList<T>::Select(T&x,intk){ if(n<=0||k>n||k<=0)returnOutOfBounds; intj=Select(k,0,n-1,5); x=l[j];returnSuccess;}

template<classT>intSortableList<T>::Select(intk,intleft,intright,intr){intn=right-left+1;if(n<=r){InsertSort(left,right);returnleft+k-1;

}

for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);}intj=Select(Ceil(n/r,2),left,left+(n/r)-1,r);Swap(left,j);j=Partition(left,right);if(k==j-left+1)returnj;elseif(k<j-left+1)returnSelect(k,left,j-1,r);elsereturnSelect(k-(j-left+1),j+1,right,r);}5.5.4時間分析

以二次取中的中間值mm為主元，經(jīng)過一趟分劃，左、右兩個子表的大小均至多為：

n

n/r

/2

r/2

設T(n)為當表長為n時執(zhí)行程序5－14所需的時間。T(n)由三部分時間組成：

T(n)

T(

n/5

)+T(3n/4)+cn

用歸納法容易證明，T(n)

20cn，n

1是線性時間的。

5.5.5允許重復元素的選擇算法由于允許包含相同元素，左子表中除了小于mm的元素外，還包含與mm相同值的元素。因此，左子表的大小至多可達

n

n/r

/2

r/2

+1/2

n/r

/2

r/2

=n-1/2

n/r

/2

r/2

容易用歸納法證明對于所有n

90，

T(n)

T(n/9)+T(7n/8)+cn

72cn，n

90

5.6斯特拉森矩陣乘法

問題矩陣相乘

5.6.1分治法求解

C11＝A11B11+A12B21C12＝A11B12+A12B22C21＝A21B11+A22B21C22＝A21B12+A22B22

T(n)=

(n3)5.6.2

斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)

C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)=

(nlog7)

(n2.81)

算法設計與分析

——C++語言描述DeSignandAnalysisofAlgorithmsInC++

第2部分算法設計策略

第6章貪心法

6.1一般方法

6.2背包問題

6.3帶時限的作業(yè)排序

6.4最佳合并模式

6.5最小代價生成樹

6.6單源最短路徑

6.7磁帶最優(yōu)存儲

6.8貪心法的基本要素6.1一般方法

最優(yōu)化問題（optimizationproblems）是指這樣一類問題，問題給定某些約束條件（constraint），滿足這些約束條件的問題解稱為可行解（feasiblesolution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數(shù)值函數(shù)，稱為目標函數(shù)（objectivefunction），使目標函數(shù)取最大（或最?。┲档目尚薪夥Q為最優(yōu)解（optimalsolution）。

貪心法是通過分步?jīng)Q策（stepwisedecision）的方法來求解問題的。貪心法每一步上用作決策依據(jù)的選擇準則被稱為最優(yōu)量度標準（optimizationcriterion）。在根據(jù)最優(yōu)量度標準選擇分量的過程中，還需要使用一個可行解判定函數(shù)。貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當前看似最佳選擇，必須進一步證明該算法最終導致問題的一個整體最優(yōu)解。

【程序6－1】貪心法SolutionTypeGreedy(STypea[],intn){ SolutionTypesolution=

; for(inti=0;i<n;i++){ STypex=Select(a); if(Feasiable(solution,x)) solution=Union(solution,x); } returnsolution;}6.2背包問題

問題在一個元素集合中尋找最大元素和最小元素的問題。6.2.1

問題描述

已知一個載重為M的背包和n件物品，第i件物品的重量為wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi>0，pi>0，0

i<n。所謂背包問題是指求一種最佳裝載方案，使得收益最大。所以，背包問題是現(xiàn)實世界一個常見的最優(yōu)化問題。兩類背包問題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為0/1背包問題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問題或簡稱背包問題。6.2.2貪心法求解

背包問題背包問題的解可以表示成一個n-元組：X=(x0,x1,

,xn－1)，0

xi

1，0

i<n，每個xi是第i件物品裝入背包中的部分。判定可行解的約束條件是：

背包問題的最優(yōu)解必須使下列目標函數(shù)取最大值：

例6－1

設有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15)。

【程序6－2】背包問題的貪心算法

template<classT>classKnapsack{public: Knapsack(intmSize,floatcap,float*wei,T*prof);voidGreedyKnapsack(float*x);……private:floatm,*w;T*p;intn;};

template<classT>voidKnapsack<T>::GreedyKnapsack(float*x){//前置條件：w[i]已按p[i]/w[i]的非增次序排列

floatu=m;for(inti=0;i<n;i++)x[i]=0; for(i=0;i<n;i++){ if(w[i]>u)break; x[i]=1.0; u=u-w[i]; } if(i<=n)x[i]=u/w[i];}

6.2.3

算法正確性

定理6－1

如果p0/w0

p1/w1

pn－1/wn－1，則程序6－2求得的背包問題的解是最優(yōu)解。

6.3帶時限的作業(yè)排序

6.3.1

問題描述設有一個單機系統(tǒng)、無其它資源限制且每個作業(yè)運行相等時間，不妨假定每個作業(yè)運行1個單位時間?，F(xiàn)有n個作業(yè)，每個作業(yè)都有一個截止期限di>0，di為整數(shù)。如果作業(yè)能夠在截止期限之內完成，可獲得pi>0的收益。問題要求得到一種作業(yè)調度方案，該方案給出作業(yè)的一個子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調度作業(yè)運行，該子集中的每個作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說這種作業(yè)調度是最優(yōu)的。

6.3.2貪心法求解

例6－2設有4個作業(yè)，每個作業(yè)的時限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27)。

【程序6－3】帶時限作業(yè)排序的貪心算法

voidGreedyJob(intd[],SetX,intn){//前置條件：p0

p1

,…,

pn-1

X={0};for(inti=1;i<n;i++)if(集合X

{i}中作業(yè)都能在給定時限內完成)X=X

{i};}

6.3.3

算法正確性定理6－2程序6－2的貪心算法對于帶時限作業(yè)排序問題將得到最優(yōu)解。

6.3.4

可行性判定

定理6－3X=（x0,x1,…,xk）是k個作業(yè)的集合，

=（

0,

1,…,

k）是X的一種特定排列，它使得，其中，是作業(yè)

j的時限。X是一個可行解當且僅當X中的作業(yè)能夠按

次序調度而不會有作業(yè)超期。

6.3.5

作業(yè)排序貪心算法

定理6－3提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標準，即按作業(yè)收益的非增次序選擇下一