數(shù)據(jù)結(jié)構(gòu)概述

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

第三部分：算法及效率度量算法、算法的特性算法好壞的評價標(biāo)準(zhǔn)算法的性能度量方法漸進時間困難度漸進空間困難度主要內(nèi)容算法：對特定問題的求解過程的描述，是指令的有限序列，也就是為解決某一具體問題而實行的具有有限的操作步驟。程序是算法的實現(xiàn)，計算機依據(jù)程序逐步執(zhí)行算法，實現(xiàn)對問題的求解。定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列。算法五個特性：輸入有0個或多個輸入輸出有一個或多個輸出（處理結(jié)果）確定性每步定義都是精確、無歧義的有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性每一條運算應(yīng)足夠基本能被執(zhí)行算法的特性常用的設(shè)計方法：窮舉法貪心法分治法回溯法動態(tài)規(guī)劃法裁剪與分枝界限法并行算法算法的分類事例學(xué)習(xí)：選擇排序問題明確問題：非遞減排序解決方案：逐個選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-1;i++){//n-1趟

從a[i]檢查到a[n-1];

若最小的整數(shù)在a[k],交換a[i]與a[k];

}細(xì)化程序：程序SelectSort

算法設(shè)計過程

自頂向下，逐步求精

voidselectSort(inta[],constintn){//對n個整數(shù)a[0],a[1],…,a[n-1],按非遞減依次排序for(inti=0;i<n-1;i++){intk=i;//從a[i]檢查到a[n-1],找最小的整數(shù),在a[k]for(intj=i+1;j<n;j++) if(a[j]<a[k])k=j; //k指示當(dāng)前找到的最小整數(shù)inttemp=a[i];a[i]=a[k];a[k]=temp;//交換a[i]與a[k]}} 正確性（Correntness）滿足具體問題的需求，對于典型的、苛刻的一組輸入數(shù)據(jù)得到正確的結(jié)果可讀性（Readability）有利于閱讀者對程序的理解健壯性（Robustness）容錯處理效率（Efficiency）效率和低存儲需求評價算法優(yōu)劣的基本標(biāo)準(zhǔn)intsign(intx){inty;if(x>0)y=1;elseif(x=0)y=0;elsey=-1;returny;}第一個層次程序不包含語法錯誤intsign(intx){inty;if(x>1)y=1;elseif(x==0)y=0;elsey=-1;returny;}其次個層次輸入100輸出1輸入0輸出0輸入－100輸出－1intsign(intx){inty;if(x>=1)y=1;elseif(x==0)y=0;elsey=-1;returny;}第三個層次輸入100輸出1輸入1輸出1輸入0輸出0輸入-1輸出-1輸入-100輸出-1intsign(intx){inty;if(x>0)y=1;elseif(x==0)y=0;elsey=-1;

if(x==0x1234)y=0;returny;}第四個層次全部可能的輸入解決同一個問題存在多種算法，如何評估各種算法的好壞？運行算法所須要的計算機資源——時間和空間評價一個算法的優(yōu)劣的重要依據(jù)看執(zhí)行該算法的程序占用多少計算機資源程序所用算法運行時所要花費的時間代價程序中運用的數(shù)據(jù)結(jié)構(gòu)占用的空間代價如何評價？算法的后期測試：試驗方法、仿真方法算法的事前估計：分析的方法算法效率的度量試驗的方法：接受實際數(shù)據(jù)測試程序的執(zhí)行時間；仿真的方法：模擬數(shù)據(jù)進行測試；在算法中的某些部位插裝時間函數(shù)time()或者clock()測定算法完成某一功能所花費的時間。接受開發(fā)工具供應(yīng)的時間測量工具profile算法的后期測試依次搜尋(SequenialSearch)行intseqsearch(inta[],constintn, constintx)//a[0],…,a[n-1]1{2inti=0;3while(i<n&&a[i]!=x)4i++;5if(i==n)return-1;6returni;7}

插裝clock()的計時程序voidTimeSearch(){//在0..1000中搜尋0,10,…,90,100,200,…,1000inta[1001],n[20];for(intj=0;j<=1000;j++)a[j]=j;//a[1]=1,a[2]=2,…for(j=0;j<10;j++){ n[j]=10*j;//n[0]=0,n[1]=10,n[2]=20n[j+10]=100*(j+1);}//n[10]=100,n[11]=200,n[12]=300...printf("%12s%12s%12s\n","n","500000","1");

for

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

clock_t

start,stop; start=clock();

longcount=500000;

while(count--)

int

k=seqsearch(a,1001,n[j]);

stop=clock();

doublerunTime=stop–start;

printf(“%12d%12d%12.6f\n”,n[j],runTime,

double(runTime)/500000);

}

}程序測試結(jié)果輸出程序在計算機上運行所需時間的影響因素算法本身選用的策略問題的規(guī)模規(guī)模越大，消耗時間越多書寫程序的語言語言越高級，消耗時間越多編譯產(chǎn)生的機器代碼質(zhì)量機器執(zhí)行指令的速度為便于比較算法本身的優(yōu)劣應(yīng)解除其它影響算法效率的因素希望軟件執(zhí)行時間可預(yù)料算法分析感愛好的不是具體的資源占用量，而是與具體的平臺無關(guān)、具體的輸入實例無關(guān)，且隨著規(guī)模增長的值是可預(yù)料的。算法的事前估計希望了解軟件執(zhí)行時間的變更趨勢與問題規(guī)模之間的關(guān)系，用確定的規(guī)模數(shù)據(jù)作為輸入時程序所需的基本操作的次數(shù)來描述時間效率忽視微小環(huán)節(jié)完成一個基本操作所須要的時間應(yīng)當(dāng)與具體的被操作數(shù)無關(guān)算法的困難性分析例以迭代方式求累加和的函數(shù)行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(

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

4

s+=a[i];

5

returns;

6

}

程序步確定方法

插入計數(shù)全局變量count

建表，列出個語句的程序步計算累加和程序

程序步數(shù)計算工作表格

語句執(zhí)行的頻度2n+3程序的精確步數(shù)沒有實際意義，程序步數(shù)的數(shù)量級別可以反映程序的實質(zhì)。n：一個特定算法的“運行工作量”的大小，只依靠于問題的規(guī)模（通常用整數(shù)量n表示）f(n):算法中基本操作的執(zhí)行次數(shù)，即它是問題規(guī)模的函數(shù)。算法的漸進時間困難度，簡稱算法時間困難度記作：

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

表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率與f(n)的增長率相同。表示算法執(zhí)行時間的增長的數(shù)量級。時間困難度的漸進表示法大O表示法定義當(dāng)N≥N0時存在一個正的常數(shù)c和N0，使得T(n)≤cF(n),則（Big-Oh）T(N)就是O(F(n))含義：當(dāng)n增大時，算法的運行時間的增長率小于等于Ｆ(n)的增長率。算法的漸進分析就是要估計，當(dāng)數(shù)據(jù)規(guī)模逐步增大時資源開銷f(n)的增長趨勢，得到一個精確的界限比較費時費勁，也沒有必要時間困難度的漸進表示法從數(shù)量級大小比較來考慮，當(dāng)n增到到確定值后，對資源開銷影響最大的就是n的冪次最高的項，所以運用Big-Oh表示法時不必考慮常數(shù)、系數(shù)、次要項和關(guān)系符號。O(n2)√O(2n2+2n+1)×常見的算法時間困難度：1<log2n<n<nlog2n<n2<n3<2n<3n<n!算法時間困難度的分析規(guī)則依據(jù)程序的結(jié)構(gòu)分析時間困難度時間困難度的漸進表示法加法規(guī)則針對并列程序段：依次結(jié)構(gòu)，if結(jié)構(gòu)，switch結(jié)構(gòu)T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))乘法規(guī)則針對嵌套程序段；for，while，dowhile

T(n,m)=T1(n)*T2(m)

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

時間困難度計算例1：x++;s=0; 用頻度法分析：將x++看成是基本操作，語句頻度為１ T(n)=2 算法的時間困難度：O(1)---常量階例2:for(i=0;i<n;i++){ //執(zhí)行n+1次x++;//語句頻度為：ns+=x;//語句頻度為：n} T(n)=2n+n+1=3n+1，則時間困難度為：O(n) 也可以這樣考慮：將x自增看成是基本操作，則語句頻度為：n其時間困難度為：O(n)，即時間困難度為線性階。例3:矩陣相乘C=AxBfor(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}T(n)=2n3+3n2+2n+1算法的時間困難度：O(n3)計算方法1：由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為:n×n×n=n3故時間困難度為T(n)=O(n3)。計算方法2：由于“乘法”運算是本例的基本操作，故整個算法的執(zhí)行時間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)n3成正比，故時間困難度為T(n)=O(n3)。時間困難度計算1-26

例4:分析以下程序段的時間困難度 i=1;//語句頻度為：１ while(i<=n) i=i*2//語句頻度為：f(n) 因為：２f(n)≤n，即：f(n)≤log2n，取最大值f(n)=log2n，則該程序的時間困難度為： T(n)=1+f(n)=1+log2n=O(log2n)時間困難度計算1-27

時間困難度計算算法中基本操作重復(fù)執(zhí)行的次數(shù)隨問題的輸入數(shù)據(jù)集不同而不同例6：在數(shù)組A[n]查找給定值K(1)i=0;(2)while(i<=n-1&&A[i]!=K)(3)i=i+1;(4)returni;最好狀況的時間困難度T(n)=O(1)A[0]等于K最壞狀況的時間困難度T(n)=O(n)A[n-1]等于Ｋ平均時間困難度： 全部可能的輸入實例以等概率出現(xiàn)的狀況T(n)=(1+2+...+n)/n 算法的時間困難度：O(n)1-28

時間困難度按數(shù)量遞增排列及增長率一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)指數(shù)時間的關(guān)系為：O(nk)<O(2n)<O(n!)<O(nn)當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上特殊懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個宏大的成就。增長率函數(shù)曲線存儲空間的固定部分

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

尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過new和delete叮囑動態(tài)運用的空間空間困難度的度量只考慮程序運用的可變部分空間運用狀況空間困難度度量漸進的空間困難度一個算法為解決問題所用幫助存儲空間的大小，只依靠于問題的規(guī)模（通常用整數(shù)量n表示），即它是問題規(guī)模的函數(shù)。算法的漸進空間困難度，簡稱算法空間困難度記作：

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

表示最壞狀況下，算法所需幫助存儲空間的數(shù)量是實例特性n的某個函數(shù)的數(shù)量級，表示所需存儲空間增長的數(shù)量級。例解法1先計算x的冪,存于power[]中,再分別乘以相應(yīng)的系數(shù)#