計算機算法設計與分析

第一章緒論計算機與軟件學院（Schoolof

ComputerandSoftware）NanjingUniversityofInformationScience&Technology第一章緒論

1.1算法的概念及其特性

1.2衡量算法性能的標準1.3算法的時間和空間復雜度1.4算法分析1.5最優(yōu)算法1.6高效算法的必要性“算法設計與分析”主要研究內容是：如何通過計算機將一個給定的輸入高效地轉化為所需要的輸出。包括：

算法設計算法分析1.1算法的概念及其特性算法（Algorithm）：對特定問題求解步驟的一種描述，是指令的有限序列。一、算法的定義算法的形式化定義：算法是一個四元組(Q,I,Ω,F)其中：Q是包含子集I和Ω的集合,表示計算的狀態(tài).

I、Ω分別表示計算的輸入、輸出集合.

F表示計算的規(guī)則,它是一個由Q到它自身的函數,且具有自反性,即對于任何qQ,有F(q)=q.computer輸入輸出問題算法抽象二、算法的特性算法的5個特性：輸入：有零個或多個外部量作為算法的輸入。輸出：算法產生至少一個量作為輸出。確定性(definiteness)：組成算法的每條指令清晰、無歧義。有窮性(finiteness)：算法中每條指令的執(zhí)行次數有限，執(zhí)行每條指令的時間也有限?？尚行?effectiveness)：算法描述的操作可以通過已經實現的基本操作執(zhí)行有限次來實現。算法與程序的區(qū)別算法是解決問題的一種方法或一個過程。一個問題可以有多種算法。程序是用某種程序設計語言對算法的具體實現。主要區(qū)別在：有窮性、描述方法

程序可以是無窮的,例如OS;而算法是有窮的.{例}程序是用程序設計語言描述,在機器上可以執(zhí)行;而算法還可以用框圖、自然語言等多種方式描述.例如操作系統，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統的各種任務可看成是單獨的問題，每一個問題由操作系統中的一個子程序通過特定的算法來實現。該子程序得到輸出結果后便終止。描述算法可以有多種方式自然語言、流程圖、偽語言等.三、算法的描述表達算法的抽象機制偽語言接近高級語言，易學、易掌握；使得設計出來的算法可讀性好，可維護性強，可靠性高；偽語言算法易于轉換為高級語言程序。算法書寫注意點:1、算法說明：通常在算法頭部之下以注釋指明：算法功能、參數含義及輸入輸出屬性；算法引用的全局變量或外部變量、其作用、初值及應滿足的限制條件等。2、適當的注釋；3、輸入與輸出：(1)scanf()、printf();(2)函數參數;(3)全局變量。4、錯誤處理：(1)函數返回狀態(tài)；(2)內部出錯處理。5、算法結構與語句選用：（1）分支、循環(huán)結構：if(switch)、while(for)（2）盡量避免用：

do{……do{……}while}while

或：

if

(…)if(…)if(…)

等結構。StatusListInsert_Sq(SqList&L,int

i,ElemTypee){/*功能:將元素e插入順序表L中。參數:L—順序表;i—元素插入位置;e—被插入表的元素。返回值:若操作成功，返回OK；否則返回ERROR*/if(i<=0||L.length)returnERROR;//i值不合法

if(L.length>=L.Listsize)//當前存儲空間已滿{//增加空間

newbase=(ElemType*)realloc(L.elem,(L.Listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新基址

L.Listsize+=LISTINCREMENT;//新的表容量

q=&(L.elem[i-1]);//插入位置for(p=&(L.elem[L.Length-1]);p>=q;--p)*(p+1)=*p;//元素后移*q=e;//插入e

L.Length++;//表長增1

returnOK;}//ListInsert_Sq舉例：順序表插入操作算法描述:四、算法與數據結構算法與數據結構的關系不了解施加于數據上的算法就無法決定如何構造數據，可以說算法是數據結構的靈魂；反之算法的結構和選擇又常常在很大程度上依賴于數據結構，數據結構則是算法的基礎。算法＋數據結構＝程序1.2衡量算法性能的標準(1)正確性(correctness)—執(zhí)行結果應當滿足功能要求。(2)可讀性(readability)—為了人的閱讀和交流。要求算法易于理解，便于分析。(3)健壯性(robustness)—輸入非法數據也能適當地作出反應或進行處理。也稱“魯棒性”。(4)效率與低存儲量－高效率、低存儲我們這里主要討論算法的時間和空間性能，并以此作為衡量算法性能的重要標準。而且我們主要側重于時間方面。時間復雜度（TimeComplexity）算法的時間復雜度：在算法運行期間所花費的時間。通常用漸進形式表示例如，T(n)=O(n2)、

Ω(n2)、Θ(n2)

空間復雜度（SpaceComplexity）

算法的空間復雜度：在算法運行期間所需要的輔助內存空間（auxiliaryspace,orworkspace）。通常用漸進形式表示例如，S(n)=O(n2)、

Ω(n2)、Θ(n2)1.3算法的時間和空間復雜度1.4算法分析

算法分析：對于算法的時間和空間復雜度進行定量分析。一、分析時間復雜度的基本步驟Step1、計算出在算法運行期間基本運算執(zhí)行的總頻數.Step2、表示為漸近時間復雜度（asymptotictimecomplexity）二、漸近符號

1.定義(大“O”符號,增長階上界)

：若存在兩個正的常數c和n0,對于任意≥n0,都有T(n)≤c×f(n)，則稱T(n)的增長階不超過f(n)的增長階,記為T(n)=O(f(n)).n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c×f(n)例：(1)設f(n)=3n,g(n)=n.因對所有n≥1,有3n≤4n,(c=4,n0=1),所以有f(n)=O(g(n)).(2)設f(n)=n+10,g(n)=n.因對所有n≥1,有n+10≤11n,(c=11,n0=1),所以有f(n)=O(g(n)).(3)設f(n)=2n2+11n-10,g(n)=n2.因對所有n≥10,有2n2+11n-10≤3n2,(c=3,n0=10),所以有f(n)=O(g(n)).(4)設f(n)=n2,g(n)=n3.因對所有n≥1,有n2≤n3,(c=1,n0=1),所以有f(n)=O(g(n)).注意到,滿足“O”符號定義的函數f(n)并不是唯一的。所以有以下約定：一個函數增長階的上界是該函數的所有上界中的最小者(忽略常數因子和低次項).例:百雞問題.“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？”

a：公雞只數，b：母雞只數，c：小雞只數。約束方程：

a+b+c=1005a+3b+c/3=100c%3=0

第一種解法：a、b、c的可能取值范圍：0~100，對在此范圍內的a、b、c的所有組合進行測試，凡是滿足上述三個約束方程的組合，都是問題的解。第二種解法：公雞只數：n/5;母雞只數：n/3;小雞只數：n-a-b。算法：改進的百雞問題輸入：所購買的三種雞的總數目n輸出：滿足問題的解的數目k,公雞,母雞,小雞的只數g[],m[],s[]1.chicken_problem(int

n,int&k,int

g[],int

m[],ints[])2.{int

k,i,j,a,b,c;3.k=0;4.i=n/5;5.j=n/3;6.for(a=0;a<=i;a++)7.for(b=0;b<=j;b++){8.c=n–a–b;9.if((5*a+3*b+c/3==n)&&(c%3==0)){10.g[k]=a;11.m[k]=b;12.s[k]=c;13.k++;14.}15.}16.}17.}

算法chicken_problem的時間花費：取n0=28，對，有：令：c=13，并令，有：所以,

含義：的增長最多象的增長那樣快。稱是的上界。運行時間的上界,“O”

2.大Ω符號(增長階下界)

定義若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≥c×g(n)，則稱T(n)的增長階不小于f(n)的增長階,記為T(n)=Ω(g(n))n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c×g(n)例：設T(n)=3n2+2n,求其增長階的下界.因對所有n>1,有|T(n)|=|3n2+2n|≥3n2,(c=3,n0=1),所以有T(n)=Ω(n2).注意到,滿足“Ω”符號定義的函數f(n)并不是唯一的。所以有以下約定：一個函數增長階的下界是該函數的所有下界中的最大者(忽略常數因子和低次項).例：百雞問題chicken_problem算法第10、

11、12、13行，僅在條件成立時才執(zhí)行,其執(zhí)行次數未知.假定條件都不成立,這些語句一次也沒有執(zhí)行.所以該算法的執(zhí)行時間至少為：當取=1時，，存在常數，和函數，使得：所以：T(n)=Ω(n2).

含義：的增長至少象的增長那樣快。表示一個解決問題的算法的時間下界。

運行時間的下界,“Ω”

3.Θ符號(增長階相同,“漸進的緊的界”)

定義若既有T(n)=O(f(n)),又有T(n)=Ω(g(n))

,則稱函數T(n)的增長階等于f(n)的增長階,記為T(n)=Θ(f(n))

n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c2×f(n)c1×f(n)例：T(n)＝5n2＋8n＋1當n≥1時，5n2＋8n＋1≤5n2＋8n＋n

＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)當n≥1時，5n2＋8n＋1≥5n2＝Ω(n2)∴當n≥1時，14n2≥5n2＋8n＋1≥5n2

則：5n2＋8n＋1＝Θ(n2)例，百雞問題chicken_problem算法，運行時間的上界是，下界是；這表明無論輸入規(guī)模如何變化，該算法的運行時間都介于和之間。表明該算法運行時間的準確界是。含義：的增長與的增長有同樣的階。表明算法的運行時間有一個較準確的界

。

運行時間的準確界,“Θ”

定理

設f,g是兩個函數,,若r為>0的常數,則f(n)=

Θ(g(n)).證：設r=c為>0的常數.由極限的定義可知,取為c/2,則必存在某個n0,當n≥n0時,總在c/2~3c/2之間.于是,對所有n≥n0時,f(n)

≤,從而

f(n)=O(g(n)).并且對所有n≥n0,有f(n)≥,從而f(n)=Ω(g(n)).

漸近符號的性質(1)和函數(對、也成立)O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；(2)傳遞性(對、也成立)f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))(3)乘積(對、也成立)O(f(n))*O(g(n))=

O(f(n)*g(n))O(cf(n))=

O(f(n))兩個函數f、g增長階的比較定義了這兩個函數之間的一個二元關系.具有的性質:性質O(f(n))+O(g(n))=

O(max{f(n),g(n)})的證明：對于任意f1(n)=

O(f(n))，存在正常數c1和自然數n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)=

O(g(n))，存在正常數c2和自然數n2，使得對所有n

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).(4)自反性f(n)=

(f(n))f(n)=O(f(n))f(n)=

(f(n))(5)對稱性f(n)=

(g(n))

g(n)=

(f(n))(6)反對稱性f(n)=O(g(n))

g(n)=

(f(n))增長階的極限形式判別法定理設f,g是兩個函數,,則(1)c≠0,f(n)與g(n)同階,f(n)=

(g(n))(2)c=0,f(n)比g(n)低階,f(n)=O(g(n))(3)c=∞,f(n)與g(n)高階,f(n)=Ω(g(n))三、算法時間復雜度的有關概念最好時間復雜度：指算法對所有可能輸入集的最小執(zhí)行時間

最壞時間復雜度：指算法對所有可能輸入集的最大執(zhí)行時間

平均時間復雜度：指算法對所有可能輸入集的執(zhí)行時間的平均值

對于算法的時間復雜度，通常從分平均、最壞、最好幾種情形來衡量，尤其是前兩種。

[例]順序查找算法以元素的比較作為基本操作?？紤]成功檢索的情況。

最好情況下的時間復雜度：

(1)

最壞情況下的時間復雜度：

(n)

在等概率前提下，平均情況下的時間復雜度：

(n)int

search(inta[],int

n,intkey){for(i=0;i<n;i++)if(a[i]==key)returni;return-1;}四、算法分析中常見的復雜度函數FunctionNamecConstantlognlogarithmicnlinernlognn-log-nn2Quadraticn3Cubic2nExponential各種數量級的f(n)五、算法漸近分析的步驟統計基本操作次數簡化、得到統計結果基本概念：漸近復雜度：O,

,

平均時間復雜度,最壞時間復雜度,最好時間復雜度基本技術：常用求和公式遞歸方程求解基本技術：根據循環(huán)統計基本操作次數用遞歸關系統計基本操作次數

統計基本操作次數的常用方法

根據循環(huán)統計基本操作的次數利用遞歸關系求基本操作的次數例：選擇排序voidsele_sort(intA[],intn){for(i=0;i<n-1;i++){index=i;for(j=i+1;j<n;j++)if(A[j]<A[index])index=j;if(index!=i){temp=A[index];

A[index]=A[i];

A[i]=temp;}}}T(n)=n*(1+(n+1)/2+1)=(n2+

5)

/2T1(n)=nT2(n)=1T3(n)=(n+1)/2T4(n)=1[例2]利用遞歸關系來基本操作的次數.求Fibonacci數列的第n項。該數列的定義為：F0=F1=1,Fi=Fi-1+Fi-2，i>=2。由這一數學定義自然地導出一個遞歸算法。int

F(intn){if(n==0||n==1)return1;elseif(n>=2)returnF(n-1)+F(n-2);}該算法的計算時間T(n)滿足遞歸方程：

T(n)=T(n-1)+T(n-2)+1,n>1；初始條件T(0)=T(1)=0。六、常用求和公式(1)算術級數(2)多項式級數平方和級數k方和級數(3)幾何級數(4)算術-幾何級數也稱遞推方程（recurrenceequation）是自然數n上一個函數T(n)，它使用一個或多個小于n時的值的等式或不等式來描述。遞推方程也稱為遞推關系或遞推式。

遞推方程必須有一個初始條件（也稱邊界條件）。七、解遞歸方程

[例]

逆序輸出正整數的各位數.voidPrintDigit(unsigned

intn){ printf(n%10); //輸出最后一位數dk

if(n>=10)PrintDigit(n/10); //以逆序輸出前k-1位數}時間分析設n=d1d2

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

n/10

是k

1位數。T(k)=2k+2=

(k)

迭代法(展開法)將遞歸方程的的右端項通過迭代展開成級數,然后估計級數和的漸進階.

生成函數(母函數)法替換法

先估計遞歸方程的顯式解,再用數學歸納法證明.主方法

若遞歸方程形如:T(n)=aT(n/b)+f(n),可根據f(n)的不同情況使用主定理.常用方法：1、展開法(Recursivelyexpand)

將遞歸方程展開直到方程右邊不再含有未知函數T，而代之以一個級數，對這個級數求和即可得到方程的解。

例：T(n)=2T(n/2)+5n2,(設n=2k);T(1)=7解：由原方程可得T(n/2)=2T(n/4)+5(n/2)2T（n/4）=2T(n/8)+5(n/4)2...T（n/2k-1）=2T(n/2k)+5(n/2k-1)2

代入原方程，得：

=…=10n2-3n[例]

使用迭代法分析程序。算法——漢諾塔算法1voidHanoi(intn,charA,charB,charC)

2{3if(n==1)

Move(A,C);//Move是一個抽象操作，表示將碟子從A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}[分析]

函數Hanoi中兩次調用自身，函數調用使用的實在參數均為n

1，函數Move所需時間具有常數界

(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）可以形象地看到遞推式的迭代過程。

[例]T(n)=2T(n/2)+n的遞歸樹2、用生成函數(母函數)解遞歸函數

1)生成函數的定義定義:令是一個數列,構造如下的函數：

該函數稱為數列a0,a1,a2,…

的生成函數.例：函數是序列的生成函數。2)生成函數的性質

(1)加法

設是序列的生成函數，

是序列的生成函數.則

是序列的生成函數。(2)移位

設是序列的生成函數，則

是序列的生成函數。(3)乘法

設是序列的生成函數，是序列的生成函數，則

是序列的生成函數，其中，

(4)z變換設是序列的生成函數，則 是序列的生成函數。當時，有：(式1)

則是序列1,1,1,…的生成函數。特別地，有：

所以，是序列的生成函數。若取數列為算法的時間復雜度函數{T(n)},則其生成函數為:

f(x)=T(0)+T(1)x+…+

T(n)xn…如果能由T(n)的遞歸方程求出T(n)的生成函數,則其展開式第n項系數即為T(n).3)用生成函數法求解遞歸方程例漢諾塔(Hanoi)問題。遞歸關系式：(式2)

用作為系數，構造一個生成函數：令：(根據式2,h(n)-2h(n-1)=1)

由式1，得：所以：令：有：解得：所以：有：，它是式中第項的系數。替換方法要求首先猜測遞推式的解，然后用歸納法證明。[例]使用替換方法分析程序Hanoi問題的時間。可以先對以下這些小的示例進行計算：T(3)=7=23

1；T(4)=15=24

1；T(5)=31=25

1；T(6)=63=26

1總結規(guī)律，猜測：T(n)=2n

1，n≥1。3、替換法證明：（歸納法證明）(1)當n=1時，h(1)=1，結論成立。(2)歸納法假設：當k＜n時，有h(k)=2k

1.(3)那么，當k=n時，h(n)=2h(n

1)+1=2(2n

1

1)+1=2n

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

1=

(2n)。4、主方法主方法在遞歸算法分析中，常需求解如下形式的遞推式：T(n)=aT(n/c)+f(n)

式中，

a≥1和c＞1是常數，f(n)是一個漸近正函數，n/c指

n/c

或

n/c

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

[定理]

設a,b,c為非負常數,

其中n是c的冪，則其解是：(主定理)[例]T(n)=16T(n/4)+nT(1)=1對照公式:a=16,c=4,b=1,符合情況（3），[例]T(n)=2T(n/2)+n對照公式:a=2,c=2,b=1,符合情況（2），[例]T(n)=3T(n/4)+n對照公式:a=3,c=4,b=1,符合情況（1）,1.5最優(yōu)算法(optimalalgorithm)一、問題的下界定義

一個問題的下界是解決該問題的任意算法所需要的最小時間復雜度。注:

定義中的時間復雜度指最壞時間復雜度.首先對已知的解決該問題的算法進行分析,找出同類算法中共有的基本操作的最大集合.再證明這些基本操作(或其中的一些基本操作構成的子集)在最壞情況下對于該問題的解決是必不可少的.問題下界的確定?例，在一個無序數組中查找最大元的算法.輸入：數組E[],數組大小n.輸出：最大元素max.int

findMax(int[]E,intn){intmax;max=E[0];//Assumemax.for(index=1;index<n;index++)if(max<E[index])max=E[index]returnmax;}

算法findMax的最好、最壞和平均時間復雜度都一樣，為

(n).

查找無序數組最大元的所有算法的時間復雜度的下界是否是

(n)?分析：

不失一般性,只考慮數組中各元素互不相同的情形.因此n元數組中最大元只有一個.對其余n-1個元素,要判定它不是最大元,至少要找到一個比它大的元素,因此需要至少一次比較.所以,為了找出最大元,任何算法至少需要n-1次比較.由此可確定查找最大元問題的算法復雜度下界為

(n).定義如果一個算法的時間復雜度等于這個問題的下界，那么該算法是最優(yōu)的。二、最優(yōu)算法例，算法findMax即為最優(yōu)算法.例如，排序問題的計算時間下界為

(nlogn)，時間復雜度為O(nlogn)的排序算法是最優(yōu)算法。堆排序算法是最優(yōu)算法。1.6高效算法的必要性例：設算法A在輸入規(guī)模為n時的計算時間為T(n)=3×2n.在計算機C1上執(zhí)行該算法的算法是t秒.現有另一臺計算機C2,其運行速度是C1的64倍,則在C2上用算法A在t秒內能解輸入規(guī)模為多大的問題?若算法的計算時間改進為T(n)=n2,其余條件不變,則在C2上用t秒內能解輸入規(guī)模為多大的問題?解：設C2用算法A在t秒內能解n1規(guī)模的問題.則有

,得n1=n+6.設C2用改進算法在t秒內能解n2規(guī)模的問題.則有

,得n2=8n.不同時間復雜度下不同輸入規(guī)模的算法運行時間,這里假定每一個操作時間是1ns.

nlognnnlognn2n32n83n8n24n64n512n256n164n16n64n256n4.096μ65.536μ325n32n160n1.024μ32.768μ4294.967ms646n64n384n4.096μ262.144μ5.85c1287n128n896n16.384μ1997.152μ1020c2568n256n2.048μ65.536μ16.777ms1058c5129n512n4.608μ262.144μ134.218ms10135c102410n1.024μ10.24μ1048.576μ1073.742ms10289c204811n2.048μ22.528μ4194.304μ8589.935ms10589c409612n4.096μ49.152μ16.777ms68.719s101214c819213n8.196μ106.548μ67.174ms549.752s102447c1638414n16.384μ229.376μ268.435ms1.222h104913c3276815n32.768μ491.52μ1073.742ms9.773h109845c6553616n65.536μ1048.576μ4294.967ms78.187h1019709cn：納秒μ：微秒ms：毫秒s：秒h：小時d：天y：年c：世紀

算法A1A2A3A4A5A6時間復雜度nnlognn2n32nn!n2和n1的關系10n18.38n13.16n12.15n1n1+3.3n1計算機速度提高10倍后,不同算法復雜度求解規(guī)模的擴大情況

FasterComputerorFasterAlgorithm?附錄:基本數據結構復習線性結構線性表棧隊列串非線性結構樹，二叉樹圖（a1,a2,…ai-1，ai,ai＋1

，…,an）(一)線性表有關的概念：數據元素表頭ai的直接前驅ai的直接后繼下標，是元素的序號，表示元素在表中的位置n為元素總個數，即表長表尾n=0時稱為空表在數據元素的非空有限集中：（1）存在唯一的一個被稱為“第一個”的數據元素（開始結點）；（2）存在唯一的一個被稱為“最后一個”的數據元素（終端結點）；（3）除第一個之外，每個數據元素均只有一個前驅；（4）除最后一個之外，每個數據元素均只有一個后繼

.線性表的特點：邏輯地址數據元素存儲地址數據元素1a1Loc(a1)a12a2Loc(a1)+La2…………iaiLoc(a1)+(i-1)*Lai……nanLoc(k0)+(n-1)*Lan線性表的順序存儲結構

Locate(ai+1)=Locate(ai)+sizeof(ElemType)

Locate(ai)=Locate(a1)+sizeof(ElemType)*(i-1)單鏈表a4a3a1a2

0101010241014101010121014101610181020102210241026

用一組任意的存儲單元存儲線性表的各個數據元素。數據元素之間的關系通過保存直接后繼元素的存儲位置來表示。a