大二復(fù)習(xí)-數(shù)據(jù)結(jié)構(gòu)第一章緒論

什么是算法之魂？既然算法是解決問(wèn)題的辦法或法則，而解決一個(gè)問(wèn)題又不一定只有一種辦法。這樣，不同辦法之間便有了好壞之分。如何進(jìn)行比較呢？能夠進(jìn)行比較的東西很多：模塊性、正確性可維護(hù)性、功能性、友好性、簡(jiǎn)易性、可擴(kuò)展性、可靠性等等。效率（速度）——算法之魂內(nèi)容：算法的性能標(biāo)準(zhǔn)算法的后期測(cè)試算法的事前估計(jì)算法性能分析與度量目的：算法的可用性算法的性能比較讓我們從比較兩個(gè)用于查找（m個(gè)元素）的具體算法的效率開(kāi)始：順序查找和折半查找。最壞的情況下的效率：順序查找：要檢測(cè)所有m個(gè)元素；折半查找：最多檢測(cè)k+1(k=log2m)個(gè)元素。m1K1M1G順序查找10241024210243折半查找112131[例1-12]百雞問(wèn)題如果用a表示公雞的數(shù)量，b表示母雞的數(shù)量，c表示小雞的數(shù)量，則有：公雞每只5元，母雞每只3元，小雞3只1元，用100元錢買100只雞，求公雞、母雞和小雞的數(shù)量。inta,b,c,k=0;for(a=0;a<n;a++){for(b=0;b<n;b++){for(c=0;c<n;c++){if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3=0)){記錄a,b,c；k++}}}}算法一算法二inta,b,c,k=0;i=n/5;j=n/3;for(a=0;a<i;a++){\\公雞數(shù)量不超過(guò)n/5for(b=0;b<j;b++){\\母雞數(shù)量不超過(guò)n/3c=n-a-b;if((5*a+3*b+c/3)==n)&&(c%3)=0){記錄a,b,c；k++}}}當(dāng)n=100時(shí)，算法一的內(nèi)循環(huán)次數(shù)為100萬(wàn)次，而算法二的內(nèi)循環(huán)次數(shù)為21*34=714，僅為算法一的萬(wàn)分之七，有重大改進(jìn)。如果假定內(nèi)部循環(huán)一次花費(fèi)1μs的時(shí)間，則:n算法一算法二結(jié)論1001s714μs相差不大1000011天13小時(shí)6.7s相差巨大[例1-13]貨郎擔(dān)問(wèn)題窮舉法思路：如果對(duì)任意數(shù)目的n個(gè)城市分別用從1到n進(jìn)行編號(hào)，則此問(wèn)題歸結(jié)為在有向帶權(quán)圖中尋找一條路徑最短的哈密爾頓回路問(wèn)題。這里，城市間的距離可以用鄰接矩陣表示。售貨員的每一條線路，對(duì)應(yīng)于城市編號(hào)的一個(gè)排列。某售貨員要到若干個(gè)城市銷售貨物，已知各城市之間的距離。要求售貨員選擇出發(fā)的城市及旅行路線，使每一個(gè)城市僅經(jīng)過(guò)一次，最后回到出發(fā)城市，而總路程最短。intp[n],i=1;Floatcost;Min=MAX_FLOAT_NUM;while(i<n!){

產(chǎn)生n個(gè)城市的一個(gè)排列p；

cost=路線p的長(zhǎng)度；

if(cost<min){

保留p的內(nèi)容；min=cost;

}

i++;}算法需循環(huán)n!次，假設(shè)每循環(huán)一次，需花費(fèi)1μs的時(shí)間，則算法的執(zhí)行時(shí)間隨n增長(zhǎng)而增長(zhǎng)的情況如下表nn！nn！nn！5120μs131.72h1711.27year75.04ms1424h18203year9362ms1515day193857year1139.9s16242day2077146year關(guān)于算法的效率，有兩個(gè)問(wèn)題要弄清楚：用怎樣的一個(gè)量來(lái)表達(dá)一個(gè)算法的效率；對(duì)于給定的一個(gè)算法，怎樣具體評(píng)估它的效率。算法效率的估量–算法的復(fù)雜性算法的復(fù)雜性是通過(guò)算法的資源耗費(fèi)和算法所要解決的問(wèn)題的規(guī)模之間的函數(shù)關(guān)系來(lái)度量的。算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的關(guān)鍵依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說(shuō)該算法的復(fù)雜性越高（效率越低）；反之，復(fù)雜性就越低（效率越高）。計(jì)算機(jī)的資源，最重要的是時(shí)間（即CPU）和空間（即存儲(chǔ)器）資源。因而，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。不言而喻，對(duì)于任意給定的問(wèn)題，設(shè)計(jì)出復(fù)雜性盡可能低的算法是我們?cè)谠O(shè)計(jì)算法時(shí)追求的一個(gè)重要目標(biāo)。算法的復(fù)雜性影響算法執(zhí)行時(shí)間的最直接因素是所解問(wèn)題的大小；我們將算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模，用一個(gè)整數(shù)來(lái)表示；一個(gè)給定的輸入稱為問(wèn)題的實(shí)例。一般地說(shuō)，一個(gè)算法的時(shí)間耗費(fèi)和空間耗費(fèi)是問(wèn)題規(guī)模的函數(shù)；在衡量算法的復(fù)雜性時(shí)，需要對(duì)問(wèn)題實(shí)例的大小進(jìn)行量化。對(duì)于不同的問(wèn)題，量化的方法不一樣。排序問(wèn)題:待排序數(shù)據(jù)元素的個(gè)數(shù);搜索問(wèn)題:要搜索的表中的元素的個(gè)數(shù);線性方程組問(wèn)題:未知數(shù)的個(gè)數(shù);矩陣乘法問(wèn)題:兩個(gè)矩陣的行數(shù)、列數(shù);圖問(wèn)題:圖的頂點(diǎn)數(shù)和邊數(shù);等等?？臻g復(fù)雜度時(shí)間復(fù)雜度因?yàn)橛绊憟?zhí)行資源耗費(fèi)最大的因素通常是問(wèn)題的規(guī)模（即算法的輸入規(guī)模），因此，對(duì)于一個(gè)給定的輸入規(guī)模n，我們一般把算法的資源耗費(fèi)表示為n的函數(shù)。

算法復(fù)雜性度量存儲(chǔ)空間的固定部分

程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成分、對(duì)象的數(shù)據(jù)成員等)變量所占的空間可變部分

大小與實(shí)例特性有關(guān)的變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過(guò)new和delete命令動(dòng)態(tài)使用的空間空間復(fù)雜度所考慮的空間

一般是指算法工作所需要的額外的輔助存儲(chǔ)空間空間復(fù)雜度度量時(shí)間復(fù)雜度的估計(jì)1、后期測(cè)試通過(guò)在計(jì)算機(jī)上實(shí)際測(cè)試來(lái)確定算法完成某一特定功能所需的時(shí)間。2、事前估計(jì)通過(guò)對(duì)算法的分析近似地得到算法的性能。算法的后期測(cè)試基本思想：找出算法的執(zhí)行時(shí)間和問(wèn)題規(guī)模的關(guān)系。在算法中的某些部位插裝時(shí)間函數(shù)time()，測(cè)定算法完成某一功能所花費(fèi)的時(shí)間。[例1-14]順序查找算法執(zhí)行時(shí)間與實(shí)例特性有關(guān)，因此考慮最壞情況。intseqsearch(inta[],constintn,constintx){inti=0;while(i<n&&a[i])!=x)i++;if(i==n)

return-1;elsereturni;}0102030…90100200…9001000數(shù)組n測(cè)試的思路：設(shè)定問(wèn)題從小到大若干不同的規(guī)模（存放在數(shù)組中），在每一特定的規(guī)模下，執(zhí)行算法并記錄所花費(fèi)的時(shí)間。VoidTimeSearch(){inta[1001],n[20];for(intj=1;j<=1000;j++)a[j]=j;//數(shù)組a存放1，…，1000for(j=0;j<10;j++){n[j]=10*j;n[j+10]=100*(j+1);//確定每次查找的問(wèn)題規(guī)模}cout<<“ntime“<<endl;for(j=0;j<20;j++){longstart,stop;time(&start);intk=seqsearsh(a,n[j],0);//在n[j]個(gè)元素中查找time(&stop);longrunTime=stop–start;cout<<“n[j]<<“”<<runTime<<endl;}}由于time()函數(shù)的返回值的精度是有限的，所以在程序執(zhí)行時(shí)間較短時(shí)，無(wú)法得到正確結(jié)果。查找前后time()函數(shù)返回的值可能是一樣的，使得相減的結(jié)果為0。解決的辦法：采用重復(fù)n次執(zhí)行的方式得到執(zhí)行的時(shí)間，再除n得到一次執(zhí)行的時(shí)間。例如：當(dāng)問(wèn)題的規(guī)模為較小時(shí)，反復(fù)做n次查找，記錄查找前后時(shí)間之差m，再用n除m，可得平均一次查找的時(shí)間。voidTimeSearch(){inta[1001],n[20];

constlongr[20]={300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,7500,7000,6000,5000,5000};//查找的重復(fù)次數(shù)

for(intj=1;j<=1000;j++)a[j]=j;//數(shù)組a賦值

for(j=0;j<10;j++){

n[j]=10*j;n[j+10]=100*(j+1);

}cout<<“ntotalTimerunTime”<<endl;

for(j=0;j<20;j++){

longstart,stop;time(start); //開(kāi)始計(jì)時(shí)

for(longb=1;b<=r[j];b++)

intk=seqsearch(a,n[j],0);//執(zhí)行r[j]次

time(stop); //停止計(jì)時(shí)

longtotalTime=stop-start;

floatrunTime=(float)(totalTime)/(float)(r[j]);//計(jì)算一次執(zhí)行的時(shí)間

cout<<""<<n[j]<<""<<totalTime<<""<<runTime<<endl;

}}程序測(cè)試結(jié)果輸出分析可知，該算法的執(zhí)行時(shí)間與問(wèn)題的規(guī)?；境示€性關(guān)系。通過(guò)作圖法可得到相應(yīng)的直線方程。由此方程可推知最壞情況下該算法在任意問(wèn)題規(guī)模下的執(zhí)行時(shí)間。注意：用曲線構(gòu)造函數(shù)關(guān)系式，在多數(shù)情況下是比較困難的。后期測(cè)試的不足1、必須執(zhí)行程序。2、其它因素掩蓋算法本質(zhì)。3、找出問(wèn)題規(guī)模和執(zhí)行時(shí)間之間的函數(shù)關(guān)系比較困難。事前估計(jì)近似估計(jì)

——僅考慮算法中影響效率的主要因素精確估計(jì)

——統(tǒng)計(jì)算法所執(zhí)行的總的步數(shù)（若假定所有程序語(yǔ)句的執(zhí)行時(shí)間相同，均為單位時(shí)間，則總的執(zhí)行步數(shù)與總的時(shí)間相同）近似估計(jì)的例子Intlargest(intarray[],intn){inti,currlarge=0;for(i=1;i<n;i++)if(array[currlarge]<array[i])currlarge=i;returncurrlarge;}這里，問(wèn)題規(guī)模的大小為n。算法的基本操作是比較整數(shù)的值。我們假定每次比較花費(fèi)了同樣的時(shí)間c。我們僅僅需要算法執(zhí)行時(shí)間的近似估計(jì)，所以，在最壞情況下，其執(zhí)行時(shí)間近似為cn，即T(n)=cn。[例1－15]求一維數(shù)組中具有最大值的元素將一個(gè)整型數(shù)組賦給一個(gè)變量的賦值語(yǔ)句的執(zhí)行時(shí)間一般為該數(shù)組首元素地址的復(fù)制時(shí)間。無(wú)論該數(shù)組多大，我們假定此時(shí)間為c1。這樣，花費(fèi)的時(shí)間可以簡(jiǎn)單地表示為：T(n)=c1這被稱為常數(shù)時(shí)間，即輸入規(guī)模n的大小對(duì)執(zhí)行時(shí)間沒(méi)有影響。[例1－16]Sum=0;for(i=1;i<n;i++)for(j=1;j<n;j++)sum++;這個(gè)例子中的基本操作是變量sum的增量操作。我們可以假定增量操作花費(fèi)常數(shù)時(shí)間c2，這樣，我們可以估計(jì)該程序段的執(zhí)行時(shí)間為T(n)=c2n2。當(dāng)算法的執(zhí)行時(shí)間為cn時(shí)我們稱其計(jì)算時(shí)間復(fù)雜度為線性階的，當(dāng)算法的執(zhí)行時(shí)間中含有n2因子，則被稱為二次階的。如果n出現(xiàn)在指數(shù)部分，則被稱為具有指數(shù)階的時(shí)間復(fù)雜度度。[例1－17]精確估計(jì)影響程序執(zhí)行效率的因素程序設(shè)計(jì)語(yǔ)言編譯的代碼質(zhì)量機(jī)器執(zhí)行指令的速度問(wèn)題的規(guī)模程序運(yùn)行的環(huán)境程序運(yùn)行時(shí)與其他用戶的資源競(jìng)爭(zhēng)……統(tǒng)一：通過(guò)提取程序中的元操作（語(yǔ)句執(zhí)行單位時(shí)間），評(píng)價(jià)問(wèn)題規(guī)模與時(shí)間之間的關(guān)系一個(gè)算法所用的時(shí)間是它的編譯時(shí)間加上運(yùn)行時(shí)間。這里，我們只考慮算法的運(yùn)行時(shí)間。任何一個(gè)算法都是由一些“控制結(jié)構(gòu)”和若干“原操作”組成的，因此一個(gè)算法的執(zhí)行時(shí)間可以看成是所有原操作的執(zhí)行時(shí)間之和∑(原操作的執(zhí)行次數(shù)×原操作的執(zhí)行時(shí)間)。這樣，算法的執(zhí)行時(shí)間與所有原操作的執(zhí)行次數(shù)之和成正比。從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為衡量算法時(shí)間復(fù)雜度的依據(jù)。這種衡量效率的辦法所得出的不是時(shí)間量，它與軟硬件環(huán)境無(wú)關(guān)，只暴露算法本身執(zhí)行效率的優(yōu)劣。對(duì)于用程序形式描述的算法，我們用程序步作為算法的元操作。一個(gè)程序步是指在語(yǔ)法或語(yǔ)義上有意義的一段指令序列，這段指令的執(zhí)行時(shí)間與實(shí)例特性無(wú)關(guān)。1.注釋語(yǔ)句:02.聲明語(yǔ)句:03.表達(dá)式：如果表達(dá)式中不包含函數(shù)調(diào)用為1，否則要加上函數(shù)調(diào)用的程序步數(shù)。4.賦值語(yǔ)句：與表達(dá)式類似。5.循環(huán)語(yǔ)句：循環(huán)次數(shù)+16.if-else語(yǔ)句:if<expr><statement1>else<statement2>

分別將<expr>、<statement1>、<statement2>分配給每一部分。7.switch語(yǔ)句:switch(<expr>){casecond1:<statement1>casecond2:<statement2>…}首部switch(<expr>)的程序步數(shù)等于<expr>的程序步數(shù)，執(zhí)行一個(gè)條件的程序步數(shù)等于它自己的程序步數(shù)加上它前面所有條件的程序步數(shù)。8.函數(shù)執(zhí)行語(yǔ)句:

本身的步數(shù)為1，但值傳遞的參數(shù)的計(jì)算步數(shù)需要另外考慮。8.存儲(chǔ)管理語(yǔ)句:

本身的步數(shù)為1，但如調(diào)用了對(duì)象的構(gòu)造函數(shù)或析構(gòu)函數(shù)，額外的程序步數(shù)另外考慮。10.函數(shù)調(diào)用語(yǔ)句:0，其時(shí)間開(kāi)銷記入函數(shù)執(zhí)行語(yǔ)句。11.轉(zhuǎn)移語(yǔ)句:一般為1。但return<expr>需另外考慮<expr>的程序步數(shù)。

程序步確定方法插入全局計(jì)數(shù)變量count

建表，列出各個(gè)語(yǔ)句的程序步行

floatsum(floata[],constintn)

1

{

2

floats=0.0;

3

for(inti=0;i<n;i++)

4s+=a[i];

5

returns;

6

}

統(tǒng)計(jì)程序步的方法：插入全局計(jì)數(shù)變量count[例1-18]以迭代方式求累加和的函數(shù)

floatsum(floata[],constintn) {floats=0.0;count++; //count統(tǒng)計(jì)執(zhí)行語(yǔ)句條數(shù)

for(inti=0;i<n;i++){count++; //針對(duì)for語(yǔ)句

s+=a[i]; count++;//針對(duì)賦值語(yǔ)句

}

count++; //針對(duì)for的最后一次

count++; //針對(duì)return語(yǔ)句

returns;}執(zhí)行結(jié)束得程序步數(shù)計(jì)數(shù)結(jié)果：count=2×n+3。

voidsum(floata[],constintn){for(inti=0;i<n;i++)count+=2;count+=3;}

程序的簡(jiǎn)化形式floatsum(float*a,constintn){ floats=0; count++;//countisglobal for(inti=0;i<n;i++){ count++;//forfor s+=a[i]; count++;//forassignment } count++;//forlasttimeoffor count++;//forreturn returns;}Program:Program1.13withcountstatementsadded在求累加和程序中加入count語(yǔ)句注意：

一個(gè)語(yǔ)句本身的程序步數(shù)可能不等于該語(yǔ)句一次執(zhí)行所具有的程序步數(shù)。例如：賦值語(yǔ)句

x=sum(R,n);本身的程序步數(shù)為1，一次執(zhí)行對(duì)函數(shù)sum(R,n)的調(diào)用需要的程序步數(shù)為2*n+3，賦值語(yǔ)句x=sum(R,n)總的執(zhí)行的程序步數(shù)為

1+2*n+3=2*n+4linefloatrsum(float*a,constintn)1{2 if(n<=0)return0;3 elsereturn(rsum(a,n–1)+a[n-1]);4}Program:Recursivefunctionforsumfloatrsum(float*a,constintn){count++;//forifconditionalif(n<=0){count++;//forreturnreturn0;}else{count++;//forreturnreturn(rsum(a,n–1)+a[n-1]);}}Program:Withcountstatementsadded[例1-19]以遞歸方式求累加和的函數(shù)linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:Matrixaddition

voidadd(matrixa,matrixb,matrixc,intm,intn){ for(inti=0;i<m;i++){ count++;//forfori,mtimes for(intj=0;j<n;j++){ count++;//forforj,mntimes c[i][j]=a[i][j]+b[i][j]; count++;//forassignment,mntimes } count++;//forlasttimeofforj,mtimes } count++;//forlasttimeoffori,onetime}Program:Matrixadditionwithcountingstatements

[例1-20]矩陣相加linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 {4 for(intj=0;j<n;j++)5 count+=2;//2mn6 count+=2;//2m7 }8 count++;9}Program:Simplifiedprogramwithcountingonlylinevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:Matrixaddition當(dāng)問(wèn)題的規(guī)模n趨于無(wú)窮大時(shí)，把時(shí)間復(fù)雜度函數(shù)f(n)的數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度（有時(shí)簡(jiǎn)稱為時(shí)間復(fù)雜度）。注意：一個(gè)算法的“運(yùn)行工作量”通常是隨問(wèn)題規(guī)模的增長(zhǎng)而增長(zhǎng)，因此，實(shí)際比較不同算法的優(yōu)劣主要應(yīng)該以其“增長(zhǎng)的快慢”為準(zhǔn)則，算法性能評(píng)價(jià)的結(jié)果也是一個(gè)反映變化趨勢(shì)的函數(shù)(在給定規(guī)模下比較算法的優(yōu)劣沒(méi)有意義)。時(shí)間復(fù)雜度的漸進(jìn)表示法若f(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)存在兩個(gè)正的常數(shù)整數(shù)C和n0時(shí)，使得對(duì)所有的成立，則都有這時(shí)稱g(n)為f(n)的漸進(jìn)上界(asymptoticupperbound)，或稱算法的漸進(jìn)時(shí)間復(fù)雜度為：O記法注意：我們希望得到的是“盡可能緊湊”的上界若f(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)存在兩個(gè)正的整數(shù)C和n0時(shí)，使得對(duì)所有的成立，則都有這時(shí)稱g(n)為f(n)的漸進(jìn)下界。Ω記法注意：如何理解漸進(jìn)下界的意義？都有對(duì)于一個(gè)給定的函數(shù)g(n),我們記Θ(g(n))為函數(shù)的集合：Θ(g(n))={f(n):如果存在正的常數(shù)c1,c2和n0，使得當(dāng)n≥n0時(shí)，有0≤c1g(n)≤f(n)≤c2g(n)}Θ記法這可以解釋為：如果存在正的常數(shù)c1,c2，使得對(duì)于充分大的n，函數(shù)f(n)被“夾在”c1g(n)和c2g(n)之間，則函數(shù)f(n)屬于集合Θ(g(n))。因?yàn)棣?g(n))是一個(gè)集合，所以，可以記為：f(n)∈Θ(g(n))以表示f(n)是Θ(g(n))的成員。實(shí)際上，我們通常將此寫為：f(n)=Θ(g(n))以表示同樣的含義。注意：Θ、O、Ω三種記法之間具有如下關(guān)系：若f(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)有f(n)=O(g(n))和f(n)=Ω(g(n))成立,則Θ表示法比O表示法的限制性更強(qiáng)。因此，按照集合論的觀點(diǎn)，有：1.對(duì)于3n+1

取C=4，這時(shí)假設(shè)當(dāng)n≥n0時(shí)，有：3n+1≤4n，

求解n，得n≥1，取n0＝1，即當(dāng)n≥1時(shí)，3n+1≤4n

所以，3n+1=O(n)，這里n0＝1，C＝4。[例1－21]nn0f(n)=3n+14g(n)=4n完全類似地有：2.對(duì)于3n+3當(dāng)n≥3時(shí)，3n+3≤4n所以，3n+3=O(n)，這里n0＝3，C＝4。3.對(duì)于100n+6當(dāng)n≥10時(shí)，100n+6≤101n所以，100n+6=O(n)，這里n0＝10，C＝101。4.對(duì)于10n2+4n+2當(dāng)n≥5時(shí)，10n2+4n+2≤11n2所以，10n2+4n+2=O(n2)，這里n0＝5，C＝11。5.對(duì)于1000n2+100n-6當(dāng)n≥100時(shí)，1000n2+100n-6≤1001n2

所以1000n2+100n-6=O(n2)，這里n0＝100，C＝101。6.對(duì)于6×2n+n2當(dāng)n≥4時(shí)，6×2n+n2≤7×2n

所以，6×2n+n2=O(2n)，這里n0＝4，C＝7。思路：解決問(wèn)題要抓主要矛盾，解決主要矛盾著眼于矛盾的主要方面。常數(shù)階對(duì)數(shù)階線性階線性對(duì)數(shù)階平方階立方階………K次方階指數(shù)階常見(jiàn)的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排序：10n20n5nlogn2n22n時(shí)間問(wèn)題規(guī)模nloglognlognnnlognn2n32n16242425282122162563828211216224225610243.3102102132202302102464K416216220232248264K1M4.32022022424026021M1G4.93023023526029021G在給定的計(jì)算能力下問(wèn)題的規(guī)模與不同算法的執(zhí)行時(shí)間之間的關(guān)系設(shè)f(n)關(guān)于算法A的時(shí)間復(fù)雜性函數(shù)。一般說(shuō)來(lái)，當(dāng)n單調(diào)增加且趨于∞時(shí)，f(n)也將單調(diào)增加趨于∞。對(duì)于f(n)，如果存在g(n)，使得當(dāng)n→∞時(shí)有：算法的漸進(jìn)時(shí)間復(fù)雜度的解釋那么，我們就說(shuō)g(n)是f(n)當(dāng)n→∞時(shí)的漸近性態(tài)，或叫g(shù)(n)為算法A當(dāng)n→∞的漸近時(shí)間復(fù)雜度而與f(n)相區(qū)別，因?yàn)樵跀?shù)學(xué)上，g(n)是f(n)當(dāng)n→∞時(shí)的漸近表達(dá)式。直觀上，g(n)是f(n)中略去低階項(xiàng)所留下的主項(xiàng)。所以它無(wú)疑比f(wàn)(n)來(lái)得簡(jiǎn)單。簡(jiǎn)化規(guī)則：1.如果f(n)＝O(g(n))且g(n)＝O(h(n))，那么：f(n)＝O(h(n))2.如果f(n)＝O(kg(n))，這里，k>0為一常數(shù)，那么：

f(n)＝O(g(n))3.如果f1(n)＝O(g1(n))且f2(n)＝O(g2(n))，那么：f1(n)+f2(n)＝O(max(g1(n),g2(n)))4.如果f1(n)＝O(g1(n))且f2(n)＝O(g2(n)),那么：f1(n)f2(n)＝O(g1(n)×g2(n))linefloatsum(float*a,constintn)1{2 floats=0;3 for(inti=0;i<n;i++)4 s+=a[i];5 returns;6}Program:IterativefunctionforsumLines/efrequencytotal10-O(0)211O(1)31n+1O(n)41nO(n)511O(1)60-O(0)[例1－22]linefloatrsum(float*a,constintn)1{2if(n<=0)return0;3elsereturn(rsum(a,n–1)+a[n-1]);4}Program:RecursivefunctionforsumLines/efrequencytotaln=0n>0n=0n>010--0O(0)2(a)1111O(1)2(b)1101O(0)31+trmin(n-1)010O(1+trsum(n-1))40--0O(0)

trsum(n)=2O(1+trsum(n-1))[例1－23]linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:MatrixadditionLines/efrequencytotal10-O(0)21m+1O(m)31m(n+1)O(mn)41mnO(mn)50-O(0)tadd(m,n)=O(mn)[例1－24]魔方是一個(gè)從1到n2個(gè)整數(shù)的n×n矩陣，一個(gè)從1到n2個(gè)整數(shù)的n×n魔方中的每一行、每一列及對(duì)角線上的整數(shù)的和都是相同的。下面是一個(gè)n=5的魔方(和是75):15812417161475232220136432119121092251811[例1－25]1、在最上一行的中間位置填入1，然后不斷尋找下一個(gè)位置，順次填入2，3，…。2、尋找下一個(gè)位置的方向是左上；即如當(dāng)前位置是i、j，則下一個(gè)位置就是i-1，j-1。2、把平面看成是環(huán)狀的封閉體（即第一行的上方是最后一行，第一列的左方是最右一列）；3、當(dāng)前位置是i、j，如下一個(gè)預(yù)填入的位置不空，則以i+1、j作為下一個(gè)預(yù)填入的位置。492357816當(dāng)n為奇數(shù)時(shí)，H.Coxeter給出了一個(gè)生成魔方的簡(jiǎn)單規(guī)則：15872417161415232220136432119121011182529voidmagic(intn)//createamagicsquareofsizen,nisodd{constintMaxSize=51;//maximumsquaresizeintsquare[MaxSize][MaxSize],k,l;

//checkcorrectnessofnif((n>(MaxSize))||(n<1)){cerr<<“Error!…noutofrange”<<range”<<endl;return;}elseif(!(n%2)){cerr<<“Error!…niseven”<<range”<<endl;return;}//nisodd.Coxeter’srulecanbeusedfor(inti=0;i<n;i++)//initializesquareto0for(intj=0;j<n;j++)square[i][j]=0;square[0][(n-1)/2]=1;//middleoffirstrow

//iandjarecurrentpositionintkey=2;i=0;intj=(n-1)/2;n2

while(key<=n*n){//moveupandleftif(i–1<0)k=n–1;elsek=i–1;if(j–1<0)l=n–1;elsel=j–1;if(square[k][l])i=(i+1)%n;//squareoccupied,movedownelse{//square[k][l]isunoccupiedi=k;j=l;}square[i][j]=key;key++;}//endofwhile

//outputthemagicsquarecout<<“magicsquareofsize”<<n<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<square[i][j]<<““;cout<<endl;}}//Program：MagicsquareNomorethann2-1n2intBinarySearch(int*a,constintx,constintn)//Searchthesortedarraya[0],…,a[n-1]forx{for(intleft=0,right=n–1;left<=right;){//whilemoreelementsintmiddle=(left+right)/2;switch(compare(x,a[middle])){ case‘>’:left=middle+1;break;//x>a[middle] case‘<’:right=middle–1;break;//x<a[middle] case‘=’:foundx;//x==a[middle] }//endofswitch}//endofforreturn–1;//notfound}//endofBinarySearchProgram:C++functionforbinarysearch考慮二分查找函數(shù)的時(shí)間復(fù)雜度。[例1－26]實(shí)例規(guī)模是數(shù)組a中元素的個(gè)數(shù)n。循環(huán)部分每次迭代花費(fèi)的時(shí)間為O(1)。假定循環(huán)一共執(zhí)行k次迭代，在第i次迭代中需搜索的元素為n/2i-1。所以，每次迭代搜索的元素個(gè)數(shù)的序列為：這樣，循環(huán)迭代的次數(shù)一共是：log2n+1，時(shí)間復(fù)雜度為O(log2n)。voidperm(char*a,constintk,constintn)//n是元素個(gè)數(shù)//生成a[k],…,a[n-1]的所有排列{if(k==n–1){//輸出一個(gè)排列for(inti=0;i<n;i++)cout<<a[i]<<““;cout<<endl;}else{//遞歸處理for(i=k;i<n;i++){//交換a[k]和a[i]chartemp=a[k];a[k]=a[i];a[i]=temp;perm(a,k+1,n);//生成a[k+1],…,a[n-1]的所有排列//再次交換a[k]和a[i],恢復(fù)原樣temp=a[k];a[k]=a[i];a[i]=temp;}}}Program:Recursivepermutationgenerator[例1－27]從else后面的for循環(huán)可以看出，計(jì)算n個(gè)符號(hào)的全排列需要做n次對(duì)n-1個(gè)符號(hào)的遞歸求解，所以該算法執(zhí)行時(shí)間的遞歸方程為：使用替換規(guī)則，我們得到：通常只考慮三種情況下的復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別記為Tmax(N)、Tmin(N)和Tavg(N)。三種情況下的時(shí)間復(fù)雜性各從某一個(gè)角度來(lái)反映算法的效率，各有各的用處，也各有各的局限性。但實(shí)踐表明可操作性最好的且最有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜性。

計(jì)算平均時(shí)間復(fù)雜度，也就是計(jì)算大小為n的所有問(wèn)題實(shí)例的工作量的平均值。設(shè)Bn是大小為n的問(wèn)題實(shí)例的集合，I是一個(gè)實(shí)例，且大小為n，即I∈Bn，P(I)是I出現(xiàn)的概率，t(I)是算法對(duì)實(shí)例I運(yùn)行時(shí)所需要的基本運(yùn)算的執(zhí)行次數(shù)，則平均工作量為：但P(I)不是很容易確定的，因此平均工作量不易計(jì)算。為簡(jiǎn)化問(wèn)題起見(jiàn)，作等概率假設(shè)，這樣：

x=48x=50[例1－28]線性表順序查找的時(shí)間復(fù)雜度分析搜索不成功，數(shù)據(jù)比較n次。時(shí)間復(fù)雜度均為O(n)搜索成功時(shí)的平均比較次數(shù)：其中，ci為查找的是第i個(gè)元素時(shí)的比較次數(shù)，ci=

i+1。若搜索概率相等，即：p0=p1=...=pn-1=1/n，則：1、決定用哪個(gè)（或那些）參數(shù)作為輸入規(guī)模的度量。2、找出算法的基本操作（作為一個(gè)規(guī)律，它總是位于算法的最內(nèi)層循環(huán)中）。3、檢查算法的執(zhí)行次數(shù)是否只依賴于輸入規(guī)模。如果它還依賴于其他的一些特性，則最壞、平均、最好（如有必要）情況下的算法效率需要分別研究。4、建立一個(gè)算