計算機算法設計與分析

DesignandAnalysisofComputerAlgorithms

第一章算法概述10/11/20241理解算法的概念。理解什么是程序，程序與算法的區別和內在聯系。掌握算法的計算復雜性概念。掌握算法漸近復雜性的數學表述。掌握用C++語言描述算法的方法學習要點:2提綱一、算法與程序二、算法復雜性分析三、用C++語言描述算法的方法3提綱一、算法與程序二、算法復雜性分析三、用C++語言描述算法的方法41.1算法的概念算法是指解決問題的方法和過程。算法是對特定問題求解步驟的一種描述，包含操作的有限規則和操作的有限序列。通俗一點講，算法就是一個解決問題的公式（數學手冊上的公式都是經典算法）、規則、思路、方法和步驟。算法可以用自然語言描述，也可以用流程圖描述，但最終要用計算機語言編程，上機實現。

5算法是若干指令的有窮序列，滿足性質：輸入：有1個或多個滿足給定約束條件的量作為算法的輸入。輸出：算法產生至少一個量作為輸出。確定性：組成算法的每條指令是清晰，無歧義的。有限性：算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的。算法要求其執行時間是有限的(終止性)。程序的執行時間可能是無限的。(例操作系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒有作業需要處理，它仍處于動態等待中。因此，操作系統不是一個算法。

)6程序程序是某個算法或過程的在計算機上的一個具體的實現。程序是依賴于程序設計語言的，甚至依賴于計算機結構的。算法是脫離具體的計算機結構和程序設計語言的。7算法與程序的區別與聯系

(1).一個程序不一定滿足有窮性。例操作系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒有作業需要處理，它仍處于動態等待中。因此，操作系統不是一個算法。(2).程序中的指令必須是機器可執行的，而算法中的指令則無此限制。

(3).算法代表了對問題的解，而程序則是算法在計算機上的特定的實現。一個算法若用程序設計語言來描述，則它就是一個程序.8算法≠程序算法描述：自然語言，流程圖，程序設計語言，偽代碼用各種算法描述方法所描述的同一算法，該算法的功用是一樣的，允許在算法的描述和實現方法上有所不同。本書中采用類C++偽代碼語言描述算法9人們的生產活動和日常生活離不開算法，都在自覺不自覺地使用算法，例如人們到商店購買物品，會首先確定購買哪些物品，準備好所需的錢，然后確定到哪些商場選購、怎樣去商場、行走的路線，若物品的質量好如何處理，對物品不滿意又怎樣處理，購買物品后做什么等。以上購物的算法是用自然語言描述的，也可以用其他描述方法描述該算法。

10對算法的學習包括五個方面的內容：①設計算法。②表示算法。③確認算法。④分析算法。⑤驗證算法。11①設計算法。算法設計工作是不可能完全自動化的，應學習了解已經被實踐證明是有用的一些基本的算法設計方法，這些基本的設計方法不僅適用于計算機科學，而且適用于電氣工程、運籌學等領域；②表示算法。描述算法的方法有多種形式，例如自然語言和算法語言，各自有適用的環境和特點；12③確認算法。算法確認的目的是使人們確信這一算法能夠正確無誤地工作，即該算法具有可計算性。正確的算法用計算機算法語言描述，構成計算機程序，計算機程序在計算機上運行，得到算法運算的結果；④分析算法。算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。分析算法可以預測這一算法適合在什么樣的環境中有效地運行，對解決同一問題的不同算法的有效性作出比較；⑤驗證算法。用計算機語言描述的算法是否可計算、有效合理，須對程序進行測試，測試程序的工作由調試和作時空分布圖組成。

131.2問題表示設Input和Output是兩個集合。一個問題是一個關系R

Input

Output，Input稱為問題R的輸入集合，Input的每個元素稱為R的一個輸入，Output稱為問題R的輸出或結果集合，Output的每個元素稱為R的一個結果。一個算法面向一類問題，而不是僅求解問題的一個或幾個實例。141.2問題表示例如，排序（SORT）問題定義如下：－Input=

<a1,....,an>

ai是實數

－output=

<b1,....,bn>

bi是實數,且b1

...

bn

－R=

(<a1,...,an>,<b1,...,bn>)

<a1,...,an>

Input，<b1,...,bn>

output,

a1,...,an

=

b1,...,bn}15a

0,...,n-1

=5,2,4,6,1,3a

0,...,n-1

=5,2,4,6,1,3a

0,...,n-1

=2,5,4,6,1,3a

0,...,n-1

=2,4,5,6,1,3a

0,...,n-1

=2,4,5,6,1,3a

0,...,n-1

=1,2,4,5,6,3a0,...,n-1

=1,2,3,4,5,6算法的思想：撲克牌游戲1.3算法示例—插入排序算法16算法描述

1.從第一個元素開始，該元素可以認為已經被排序

2.取出下一個元素，在已經排序的元素序列中從后向前掃描

3.如果該元素（已排序）大于新元素，將該元素移到下一位置

4.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置

5.將新元素插入到該位置中

6.重復步驟2171.3算法示例插入排序算法

template<classType>voidInsertionSort(Type*a,intn)//數組a中包含了n個待排序的數.{Typekey;for(inti=1;i<n;i++){key=a[i];//Inserta[i]intothesortedsequencea[0..i-1].

intj=i-1;while(j>=0&&a[j]>key){ a[j+1]=a[j]; j--; }a[j+1]=key;}}181.4算法的正確性分析正確的算法：對于每一個輸入都最終停止,而且產生正確的輸出。不正確算法：①不停止(在某個輸入上)②對所有輸入都停止，但對某輸入產生不正確結果近似算法①對所有輸入都停止②產生近似正確的解或產生不多的不正確解算法正確性證明證明算法對所有輸入都停止證明對每個輸入都產生正確結果調試程序

程序正確性證明！程序調試只能證明程序有錯，不能證明程序無錯誤!191.4算法的正確性分析算法正確性證明的步驟：初始化算法在循環的第一步迭代開始之前，應該是正確的。保持如果在循環的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應該保持正確。終止當循環結束時，算法也應該是正確的。分析前面插入排序算法的正確性20算法設計與分析的基本方法

1.遞推法

遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的，此方法稱為遞推法。

212.遞歸

遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知

3.窮舉搜索法

窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解。

224.貪婪法

貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

235.分治法

把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

246.動態規劃法

動態規劃是一種在數學和計算機科學中使用的，用于求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎，被廣泛應用于計算機科學和工程領域。

257.迭代法

迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。26提綱一、算法與程序二、算法復雜性分析三、用C++語言描述算法的方法27同一問題可用不同算法解決，而一個算法的質量優劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮。

28二、算法復雜性分析算法復雜性=算法所需要的計算機資源所需資源量越多則復雜性越高，反之所需資源量越少則復雜性越低。其中最為重要的是：時間復雜性T(n)；空間復雜性S(n)。其中n是問題的規模（輸入大小）。示例：一維數組問題的輸入大小＝數組的長度矩陣問題的輸入大小=矩陣的維數圖論問題的輸入大小=圖的邊數/結點數29決定算法復雜性的因素算法的復雜性取決于(1)求解問題的規模；(2)具體的輸入數據；(3)算法本身的設計。若令N、I、和A分別表示問題的規模、具體的輸入和算法本身，則C=F(N,I,A)或C=FA(N,I)=F(N,I)30時間復雜性的計算時間復雜性T(N,I)的計算為：

其中：ti為執行抽象計算機的第i種指令一次所需要的時間，這里假定抽象計算機共有k種指令。ei(N,I)為經過統計后得到的執行抽象計算機的第i種指令的次數。

kT(N,I)=

ti

ei(N,I)

i=131二、算法復雜性分析算法分析的目的：設計算法——設計出復雜性盡可能低的算法選擇算法——在多種算法中選擇其中復雜性最低者322.1算法時間復雜性最壞情況下的時間復雜性

Tmax(n)=max{T(I)|size(I)=n}最好情況下的時間復雜性

Tmin(n)=min{T(I)|size(I)=n}平均情況下的時間復雜性

Tavg(n)=

其中I是問題的規模為n的實例，p(I)是實例I出現的概率。332.2時間復雜性計算為了能夠較客觀的反映出一個算法的效率，在度量一個算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與算法實現過程中的許多細節無關。為此，可以用算法在執行過程中所需基本運算的執行次數來度量算法的工作量。基本運算反映了算法運算的主要特征，因此，用基本運算的次數來度量算法工作量是客觀的也是實際可行的，有利于比較同一問題的幾種算法的優劣。例如，在考慮兩個矩陣相乘時，可以將兩個實數之間的乘法運算作為基本運算.342.2時間復雜性計算在一般的計算機系統中，基本的運算和操作有以下四類：

①算術運算：主要包括加、減、乘、除等運算。

②邏輯運算：主要包括“與”、“或”、“非”等運算。

③關系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算。

④數據傳輸：主要包括賦值、輸入、輸出等操作。規定其中每條指令所需的時間都為常量。算法的執行時間=原子操作的執行次數×原子操作的執行時間35

template<classType>voidInsertionSort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}2.2時間復雜性計算36在最好情況下，ti=1,for1

i<n;在最壞情況下，ti

＝

i+1,for1

i<n;2.2時間復雜性計算37算法的時間復雜度

如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上(n-1)次。平均來說插入排序算法的時間復雜度為O(n2)。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。

38復雜性分析的簡化令T(N)為表示算法A的復雜性函數，若存在?(N)，使得LimN

(T(N)–?(N))/T(N)=0

那么，就可以用?(N)來代替T(N)，從而簡化復雜性的分析。例如：T(N)=3N2+4NlogN+7，?(N)=3N2，則

LimN

(T(N)–?(N))/T(N)=LimN

4NlogN+7/3N2+4NlogN+7=039用階來表示復雜性在漸進復雜性分析中，只要關心?(N)的階就夠了，不必關心?(N)中的常數因子，這樣我們就只需要用?(N)的階來表示該算法的復雜性。例如，計算一個N維矩陣A的平方的時間復雜性可估算為2N*N2=2N3，即此計算的時間復雜性為3階。402.3時間復雜性的漸近性態時間復雜性的漸近性態：

(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的漸近性態，為算法的漸近復雜性。在數學上，t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡單。41幾個記號設f(N)、g(N)都是定義在正整數集上的函數。上界記號O：如果存在正的常數C和自然數N0，使得當N≧N0

時有f(N)≦Cg(N)，則f(N)有上界函數g(N)，記為f(N)=O(g(N))。下界記號Ω：如果存在正的常數C和自然數N0，使得當N≧N0

時有f(N)≧Cg(N)，則f(N)有下界函數g(N)，記為f(N)=Ω(g(N))。同階記號Θ：f(N)=Θ(g(N))表示f(N)和g(N)同階。低階記號o：f(N)=o(g(N))表示f(N)比g(N)低階422.3時間復雜性的漸近性態漸近上界記號OO(g(n))={f(n)|存在正常數c和n0使得對所有n

n0有：

0

f(n)

cg(n)}例如：3n-10=O(n);n2+2n+3=O(n2);3logn+loglogn=O(logn);常數=O(1)432.3時間復雜性的漸近性態大O的運算性質：O(f)+O(g)=O(max(f,g));O(f)+O(g)=O(f+g);O(f)O(g)=O(fg);如果g(n)=O(f(n)),則O(f)+O(g)=O(f);O(cf(n))=O(f(n)),其中c是一個正的常數；f=O(f);如果f(n)是次數為d的多項式，即f(n)=adnd+…+a1n+a0，則f(n)=O(nd)在大O符號中包含常數因子和低階項被認為是不好的。應該用大O的最簡單形式描述算法的時間復雜性。應該用大O符號盡可能接近地表征一個函數。442.3時間復雜性的漸近性態漸近下界記號

(g(n))={f(n)|存在正常數c和n0使得對所有n

n0有：0

cg(n)

f(n)}漸近確界記號⊙

當且僅當f(n)=O(g(n))且f(n)=(g(n))，定義f(n)=⊙(g(n))。表示f(n)與g(n)同階。452.3時間復雜性的漸近性態非緊上界記號o

若對于任意正常數c>0，存在常數n0>0，當n>=n0時，滿足0f(n)cg(n)，則稱f(n)=o(g(n))。非緊下界記號

若對于任意正常數c>0，存在常數n0>0，當n>=n0時，滿足0cg(n)f(n)，則稱f(n)=

(g(n))。例如，f(n)=12n2+6n=o(n3)=(n)直觀上，o(.)在漸近意義上類似于“小于”，(.)在漸近意義上類似于“大于”。462.4非遞歸算法分析例1：交換i和j的內容

Temp=i；i=j；j=temp；

以上三條單個語句的執行次數均為1，該算法段的執行時間是一個與問題規模n無關的常數。算法的時間復雜度為常數階，記作T(n)=Ο(1)。472.4非遞歸算法分析例2：求數組最小值

int

ArrayMin(inta[],intn){min=a[0];for(i=1;i<n;i++)if(a[i]<min)min=a[i];returnmin;}

循環體內計算時間*循環次數。如果循環變量與問題規模n有關，則時間復雜度一般為O(n)。

482.4非遞歸算法分析例3：嵌套循環情況

(1)x=0；y=0；

(2)for(k=1；k<=n；k++)(3)x++；

(4)for(i=1；i<=n；i++)(5)for(j=1；j<=n；j++)(6)y++；

該算法段的時間復雜度為T(n)=Ο(n2)。

當有若干個嵌套循環語句時，算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的執行次數決定的。492.4非遞歸算法分析例4：嵌套循環情況for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j]; }該算法時間復雜度為O(n3

)50非遞歸算法的基本法則：順序語句：各語句計算時間相加；for/while循環：循環體內計算時間*循環次數；嵌套循環：

最深層循環體內計算時間*所有循環次數；if-else語句：

if語句計算時間和else語句計算時間的較大者。2.4非遞歸算法分析512.5遞歸算法分析遞歸算法：建立遞歸方程;遞推（迭代）求解例1：求n!int

factorial(intn){if(n==0)return1;returnn*factorial(n-1);}52?íì>+==15)2(217)(2nnnTnnT)(2nO=222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×′+++=+++=++=+=--L2.5遞歸算法分析例2：53例線性對數階O(log2n)：

i=1;

①

while(i<=n)

i=i*2;②解：語句1的頻度是1,

設語句2的頻度是f(n),

則：2^f(n)<=n;f(n)<=log2n

取最大值f(n)=log2n,

T(n)=O(log2n)54Ο(1)稱為常數級Ο(logn)稱為對數級Ο(n)稱為線性級Ο(nc)稱為多項式級Ο(cn)稱為指數級Ο(n!)稱為階乘級(n為問題的規模,c為一常量)2.6算法復雜性的一般表示形式低高時間復雜性55提綱一、算法與程序二、算法復雜性分析三、用C++語言描述算法的方法56用c++描述算法57（1）選擇語句：（1.1)if語句：（1.2)？語句：

if(expression)statement;elsestatement;

exp1?exp2:exp3y=x>9?100:200;等價于：

if(x>9)y=100;elsey=200;58（1.3)switch語句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}59（2）迭代語句：（2.1)for循環：

for(init;condition;inc)statement;（2.2)while循環：

while(condition)statement;（2.3)do-while循環：

do{statement;}while(condition);60（3）跳轉語句：（3.1)return語句：

returnexpression;（3.2)goto語句：

gotolabel;

label:61（4）函數：例：

return-typefunctionname(para-list){bodyofthefunction}

int

max(int

x,inty)