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

第一章緒論計(jì)算機(jī)與軟件學(xué)院（Schoolof

ComputerandSoftware）NanjingUniversityofInformationScience&Technology第一章緒論

1.1算法的概念及其特性

1.2衡量算法性能的標(biāo)準(zhǔn)1.3算法的時(shí)間和空間復(fù)雜度1.4算法分析1.5最優(yōu)算法1.6高效算法的必要性“算法設(shè)計(jì)與分析”主要研究?jī)?nèi)容是：如何通過計(jì)算機(jī)將一個(gè)給定的輸入高效地轉(zhuǎn)化為所需要的輸出。包括：

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

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

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

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

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

或：

if

(…)if(…)if(…)

等結(jié)構(gòu)。StatusListInsert_Sq(SqList&L,int

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

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

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

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

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++;//表長(zhǎng)增1

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

Ω(n2)、Θ(n2)

空間復(fù)雜度（SpaceComplexity）

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

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

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

1.定義(大“O”符號(hào),增長(zhǎng)階上界)

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

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

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

第一種解法：a、b、c的可能取值范圍：0~100，對(duì)在此范圍內(nèi)的a、b、c的所有組合進(jìn)行測(cè)試，凡是滿足上述三個(gè)約束方程的組合，都是問題的解。第二種解法：公雞只數(shù)：n/5;母雞只數(shù)：n/3;小雞只數(shù)：n-a-b。算法：改進(jìn)的百雞問題輸入：所購(gòu)買的三種雞的總數(shù)目n輸出：滿足問題的解的數(shù)目k,公雞,母雞,小雞的只數(shù)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的時(shí)間花費(fèi)：取n0=28，對(duì)，有：令：c=13，并令，有：所以,

含義：的增長(zhǎng)最多象的增長(zhǎng)那樣快。稱是的上界。運(yùn)行時(shí)間的上界,“O”

2.大Ω符號(hào)(增長(zhǎng)階下界)

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

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

含義：的增長(zhǎng)至少象的增長(zhǎng)那樣快。表示一個(gè)解決問題的算法的時(shí)間下界。

運(yùn)行時(shí)間的下界,“Ω”

3.Θ符號(hào)(增長(zhǎng)階相同,“漸進(jìn)的緊的界”)

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

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

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

＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)當(dāng)n≥1時(shí)，5n2＋8n＋1≥5n2＝Ω(n2)∴當(dāng)n≥1時(shí)，14n2≥5n2＋8n＋1≥5n2

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

。

運(yùn)行時(shí)間的準(zhǔn)確界,“Θ”

定理

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

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

≤,從而

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

漸近符號(hào)的性質(zhì)(1)和函數(shù)(對(duì)、也成立)O(f(n))+O(g(n))=

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

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

(h(n))

f(n)=O

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

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

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

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

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

n1，有f1(n)

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

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

n2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的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)對(duì)稱性f(n)=

(g(n))

g(n)=

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

g(n)=

(f(n))增長(zhǎng)階的極限形式判別法定理設(shè)f,g是兩個(gè)函數(shù),,則(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))三、算法時(shí)間復(fù)雜度的有關(guān)概念最好時(shí)間復(fù)雜度：指算法對(duì)所有可能輸入集的最小執(zhí)行時(shí)間

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

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

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

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

最好情況下的時(shí)間復(fù)雜度：

(1)

最壞情況下的時(shí)間復(fù)雜度：

(n)

在等概率前提下，平均情況下的時(shí)間復(fù)雜度：

(n)int

search(inta[],int

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

,

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

統(tǒng)計(jì)基本操作次數(shù)的常用方法

根據(jù)循環(huán)統(tǒng)計(jì)基本操作的次數(shù)利用遞歸關(guān)系求基本操作的次數(shù)例：選擇排序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]利用遞歸關(guān)系來基本操作的次數(shù).求Fibonacci數(shù)列的第n項(xiàng)。該數(shù)列的定義為：F0=F1=1,Fi=Fi-1+Fi-2，i>=2。由這一數(shù)學(xué)定義自然地導(dǎo)出一個(gè)遞歸算法。int

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

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

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

[例]

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

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

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

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

n/10

是k

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

(k)

迭代法(展開法)將遞歸方程的的右端項(xiàng)通過迭代展開成級(jí)數(shù),然后估計(jì)級(jí)數(shù)和的漸進(jìn)階.

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

先估計(jì)遞歸方程的顯式解,再用數(shù)學(xué)歸納法證明.主方法

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

將遞歸方程展開直到方程右邊不再含有未知函數(shù)T，而代之以一個(gè)級(jí)數(shù)，對(duì)這個(gè)級(jí)數(shù)求和即可得到方程的解。

例：T(n)=2T(n/2)+5n2,(設(shè)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是一個(gè)抽象操作，表示將碟子從A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}[分析]

函數(shù)Hanoi中兩次調(diào)用自身，函數(shù)調(diào)用使用的實(shí)在參數(shù)均為n

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

(1)，可將其視為一個(gè)程序步，于是有：擴(kuò)展并計(jì)算此遞推式：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、用生成函數(shù)(母函數(shù))解遞歸函數(shù)

1)生成函數(shù)的定義定義:令是一個(gè)數(shù)列,構(gòu)造如下的函數(shù)：

該函數(shù)稱為數(shù)列a0,a1,a2,…

的生成函數(shù).例：函數(shù)是序列的生成函數(shù)。2)生成函數(shù)的性質(zhì)

(1)加法

設(shè)是序列的生成函數(shù)，

是序列的生成函數(shù).則

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

設(shè)是序列的生成函數(shù)，則

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

設(shè)是序列的生成函數(shù)，是序列的生成函數(shù)，則

是序列的生成函數(shù)，其中，

(4)z變換設(shè)是序列的生成函數(shù)，則 是序列的生成函數(shù)。當(dāng)時(shí)，有：(式1)

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

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

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

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

用作為系數(shù)，構(gòu)造一個(gè)生成函數(shù)：令：(根據(jù)式2,h(n)-2h(n-1)=1)

由式1，得：所以：令：有：解得：所以：有：，它是式中第項(xiàng)的系數(shù)。替換方法要求首先猜測(cè)遞推式的解，然后用歸納法證明。[例]使用替換方法分析程序Hanoi問題的時(shí)間?？梢韵葘?duì)以下這些小的示例進(jìn)行計(jì)算：T(3)=7=23

1；T(4)=15=24

1；T(5)=31=25

1；T(6)=63=26

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

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

1.(3)那么，當(dāng)k=n時(shí)，h(n)=2h(n

1)+1=2(2n

1

1)+1=2n

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

1=

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

式中，

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

n/c

或

n/c

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

[定理]

設(shè)a,b,c為非負(fù)常數(shù),

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

一個(gè)問題的下界是解決該問題的任意算法所需要的最小時(shí)間復(fù)雜度。注:

定義中的時(shí)間復(fù)雜度指最壞時(shí)間復(fù)雜度.首先對(duì)已知的解決該問題的算法進(jìn)行分析,找出同類算法中共有的基本操作的最大集合.再證明這些基本操作(或其中的一些基本操作構(gòu)成的子集)在最壞情況下對(duì)于該問題的解決是必不可少的.問題下界的確定?例，在一個(gè)無序數(shù)組中查找最大元的算法.輸入：數(shù)組E[],數(shù)組大小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的最好、最壞和平均時(shí)間復(fù)雜度都一樣，為

(n).

查找無序數(shù)組最大元的所有算法的時(shí)間復(fù)雜度的下界是否是

(n)?分析：

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

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

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

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

,得n2=8n.不同時(shí)間復(fù)雜度下不同輸入規(guī)模的算法運(yùn)行時(shí)間,這里假定每一個(gè)操作時(shí)間是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：小時(shí)d：天y：年c：世紀(jì)

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

FasterComputerorFasterAlgorithm?附錄:基本數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)線性結(jié)構(gòu)線性表?xiàng)ｊ?duì)列串非線性結(jié)構(gòu)樹，二叉樹圖（a1,a2,…ai-1，ai,ai＋1

，…,an）(一)線性表有關(guān)的概念：數(shù)據(jù)元素表頭ai的直接前驅(qū)ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)表尾n=0時(shí)稱為空表在數(shù)據(jù)元素的非空有限集中：（1）存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素（開始結(jié)點(diǎn)）；（2）存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素（終端結(jié)點(diǎn)）；（3）除第一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；（4）除最后一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼

.線性表的特點(diǎn)：邏輯地址數(shù)據(jù)元素存儲(chǔ)地址數(shù)據(jù)元素1a1Loc(a1)a12a2Loc(a1)+La2…………iaiLoc(a1)+(i-1)*Lai……nanLoc(k0)+(n-1)*Lan線性表的順序存儲(chǔ)結(jié)構(gòu)

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

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

0101010241014101010121014101610181020102210241026

用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素之間的關(guān)系通過保存直接后繼元素的存儲(chǔ)位置來表示。a