北京工業(yè)大學(xué)：數(shù)據(jù)結(jié)構(gòu)與算法分析 教學(xué)課件第十章 算法設(shè)計與分析導(dǎo)論

數(shù)據(jù)結(jié)構(gòu)與C/C++&Java北京工業(yè)大學(xué)計算機學(xué)院軟件學(xué)科部陳文博

2004數(shù)據(jù)結(jié)構(gòu)與算法1第十章算法設(shè)計與分析導(dǎo)論數(shù)據(jù)結(jié)構(gòu)與算法2主要內(nèi)容

算法設(shè)計與分析內(nèi)容介紹算法分析的方法遞歸與分治算法回溯算法貪心算法

數(shù)據(jù)結(jié)構(gòu)與算法3算法設(shè)計與分析內(nèi)容介紹從引例看算法設(shè)計表達算法的抽象機制數(shù)學(xué)算法與數(shù)據(jù)結(jié)構(gòu)算法算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系算法分析的方法常用算法模式數(shù)據(jù)結(jié)構(gòu)與算法4010203040506071234四染色地理結(jié)論的實現(xiàn)123456712345670111111100011010011001010100111101111001011000110從引例看算法設(shè)計11數(shù)據(jù)結(jié)構(gòu)與算法5BacktrackingAlgorithmIdea數(shù)據(jù)結(jié)構(gòu)與算法6publicbooleanbacktrack(){

Stack

S=newArrayStack();//Initializesystem;i=1;//the

i

isnumberofatask

j=1;//the

j

isitemnumberofchoice

do{

}(!wholeprojecthascompleted)}//accomplishbacktrack數(shù)據(jù)結(jié)構(gòu)與算法7do{while((!Thechoiceexceedsthescope)&&(!wholeprojecthascompleted)){

if(!matchConstraint(i,j))j++;

elsebreak;}

if(!Thechoiceexceedsthescope){

S.push((i,j));i++;j=1;//newtaskinbeginning}elseif(!S.empty()){(i,j)=S.pop();j++;//testnewchoice}elsereturn

false;

if(wholeprojecthascompleted))return

true;}(!wholeprojecthascompleted)數(shù)據(jù)結(jié)構(gòu)與算法8

ADT

Stack

{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底。

}ADTStack

基本操作：

Stack()

empty()

push(e)

pop()數(shù)據(jù)結(jié)構(gòu)與算法9表達算法的抽象機制數(shù)

據(jù)

模

型初始狀態(tài)結(jié)果狀態(tài)算

法頂層算法底層算法宏觀步驟

算法骨干變量抽象

運算粗化微觀步驟

算法細節(jié)變量具體

運算細化ADT(抽象)運算步驟數(shù)據(jù)結(jié)構(gòu)與算法10數(shù)學(xué)層面的算法與數(shù)據(jù)結(jié)構(gòu)層面的算法數(shù)據(jù)結(jié)構(gòu)層面的算法publicObjectpop(){

if(empty())

thrownewEmptyStackException();

ObjecttopElement=stack[top];

returntopElement;}涉及對具體數(shù)據(jù)結(jié)構(gòu)的操作數(shù)據(jù)結(jié)構(gòu)與算法11數(shù)學(xué)層面的算法不涉及對具體數(shù)據(jù)結(jié)構(gòu)的操作只使用數(shù)據(jù)結(jié)構(gòu)ADT的接口數(shù)據(jù)結(jié)構(gòu)與算法12算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系算法vs

抽象的邏輯的數(shù)據(jù)結(jié)構(gòu)四染色算法vs

具體的數(shù)據(jù)結(jié)構(gòu)四染色算法vs

邏輯的數(shù)據(jù)結(jié)構(gòu)

（往往由控制結(jié)構(gòu)得到體現(xiàn)）whileifelseifdo數(shù)據(jù)結(jié)構(gòu)與算法13算法分析的方法

漸進時間復(fù)雜度平均時間復(fù)雜度

一般的分析方法遞歸方程的求解數(shù)據(jù)結(jié)構(gòu)與算法14四染色算法的分析例四染色回溯算法4*4*4……4n=4nT(n)=O(4n)數(shù)據(jù)結(jié)構(gòu)與算法15voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號為1至n//的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。

if(n==1)move(x,1,z);//將編號為１的圓盤從x移到z

else{hanoi(n-1,x,z,y);

//將x上編號為１至n-1的圓盤移到y(tǒng),z作輔助塔

move(x,n,z);

//將編號為n的圓盤從x移到zhanoi(n-1,y,x,z);

//將y上編號為１至n-1的圓盤移到z,x作輔助塔

}}Hanoi塔算法的分析數(shù)據(jù)結(jié)構(gòu)與算法16T(n)T(n-1)T(n-1)O(1)T(n)=T(n-1)+O(1)+T(n-1)=2T(n-1)+O(1)遞歸方程的求解數(shù)據(jù)結(jié)構(gòu)與算法17T(n)=2T(n-1)+O(1)

=2(2T(n-2)+O(1))+O(1)

=4T(n-2)+3O(1)

=4(2T(n-3)+O(1))+3O(1)

=8T(n-3)+7O(1)

=8(2T(n-4)+O(1))+7O(1)

=16T(n-4)+15O(1)

……T(n)=2kT(n-k)+(2k-1)O(1)數(shù)據(jù)結(jié)構(gòu)與算法18T(n)=2kT(n-k)+(2k-1)O(1)n-k=1

k=n-1T(n)=2n-1T(1)+(2n-1-1)O(1)

=2n-1O(1)+(2n-1-1)O(1)

=2·2n-1O(1)-O(1)

=(2n–1)

O(1)T(n)=O(2n)

數(shù)據(jù)結(jié)構(gòu)與算法19常用算法模式遞歸與分治算法動態(tài)規(guī)劃貪心算法回溯算法分支限界算法概率算法遺傳算法數(shù)據(jù)結(jié)構(gòu)與算法20遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法21

后置遞歸法(Postponingthework)的設(shè)計思想為:假如某個問題的求解過程可以分成若干步進行，并且當(dāng)前這一步的解可以直接求得，則先求出當(dāng)前這一步的解，對于余下的問題，若問題的性質(zhì)和原問題類似，則又可遞歸求解。

數(shù)據(jù)結(jié)構(gòu)與算法22遞歸的終結(jié)狀態(tài)是，當(dāng)前的問題可以直接求解，對原問題而言，則是已走到了求解的最后一步。

鏈表是可以如此求解的一個典型例子。例如:編寫“刪除單鏈表中所有值為x

的數(shù)據(jù)元素”的算法。數(shù)據(jù)結(jié)構(gòu)與算法23

1)單鏈表是一種順序結(jié)構(gòu)，必須從第一個結(jié)點起，逐個檢查每個結(jié)點的數(shù)據(jù)元素;分析:

2)從另一角度看，鏈表又是一個遞歸結(jié)構(gòu)，若

L

是線性鏈表

(a1,a2,,an)

的頭指針，則

L->next是線性鏈表

(a2,,an)的頭指針。數(shù)據(jù)結(jié)構(gòu)與算法24

a1

a2

a3

an

…L例如:

a1

a2

a3

an

L

a1

a2

a3

an

L已知下列鏈表1)“a1=x”,則

L仍為刪除

x后的鏈表頭指針2)“a1≠x”,則余下問題是考慮以

L->next為頭指針的鏈表……

a1

L->nextL->next=p->nextp=L->next數(shù)據(jù)結(jié)構(gòu)與算法25void

delete_L(LinkList&L,ElemTypex){

//刪除以L為頭指針的帶頭結(jié)點的單鏈表中

//所有值為x的數(shù)據(jù)元素

if(L->next){

if(L->next->data==x){p=L->next;L->next=p->next;delete(p);delete_L(L,x);}

else

delete_L(L->next,x);}}//delete數(shù)據(jù)結(jié)構(gòu)與算法26void

delete_L(LinkList&L,ElemTypex){

//L為無頭結(jié)點的單鏈表的頭指針

if(L){

if(L->data=x){p=L;L=L->next;delete(p);delete_L(L,x);}

else

delete_L(L->next,x);}}4.遞歸函數(shù)中的尾遞歸容易消除。數(shù)據(jù)結(jié)構(gòu)與算法27voiddelete(LinkList&L,ElemTypex){

//L為帶頭結(jié)點的單鏈表的頭指針

p=L->next;pre=L;

while(p){

if(p->data=x){pre->next=p->next;free(p);p=pre->next;}

else{pre=p;p=p->next;}}}上述遞歸算法可改寫為迭代的形式數(shù)據(jù)結(jié)構(gòu)與算法28遞歸與分治算法數(shù)據(jù)結(jié)構(gòu)與算法29

若求解問題的規(guī)模為n

其次，逐步合并子問題的解，直到獲得原問題的解。

首先，把問題分解為k個性質(zhì)相同、但規(guī)模

較小的子問題（1kn)，并求解這些子問題。（如果這些子問題的規(guī)模還不夠“小”

，則可以進一步分解，直到可以求解為止）

分治法的概念數(shù)據(jù)結(jié)構(gòu)與算法30PP1P2Pk……T1(n)T2(n)Tk(n)T(n)時間復(fù)雜度：T(n)=T1(n)+T2(n)+……+Tk(n)+C(n)

C(n)數(shù)據(jù)結(jié)構(gòu)與算法31voidmergeSort(RcdType&SR[],ints,intt){//將SR[s..t]歸并排序

if(s==t)return;

intm=(s+t)/2;mergeSort(SR,s,m);mergeSort(SR,m+1,t);merge(SR,s,m,t);}//mergeSort例歸并排序數(shù)據(jù)結(jié)構(gòu)與算法32T(n)T(n/2)T(n/2)Cn數(shù)據(jù)結(jié)構(gòu)與算法33T(n)=T(n/2)+T(n/2)+Cn

=2T(n/2)+Cn

=2(2T(n/4)+C(n/2))+Cn

=4T(n/4)+

Cn+Cn

=4T(n/4)+2Cn

=8T(n/8)+3Cn

=2kT(n/2k)+kCn

……2k=nk=log2nT(n)=nT(1)+log2n?Cn=Cnlog2n+d

?

nT(n)=O(nlog2n)數(shù)據(jù)結(jié)構(gòu)與算法34分治算法的設(shè)計模式divide-and-conquer(P){

if(|P|)<=n0)adhocery(P);

dividePintosmallersubinstancesP1,P2,…,Pk;

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

returnmerge(y1,…,yk);}數(shù)據(jù)結(jié)構(gòu)與算法35最接近點對問題分析（直線上n個點，假設(shè)只有一對符合條件）算出每兩個點的距離.若排序,需O(n2),希望O(nlog2n)mS1S2p1p2p3q3q1q2d=min{|p1-p2|,|q1-q2|}數(shù)據(jù)結(jié)構(gòu)與算法36publicstaticdoublenearPair(S){n=|S|;

if(n<2)return;m=S中各點坐標(biāo)的中位數(shù)；

構(gòu)造S1和S2；

//S1={x?S|x<=m},S2={x?S|x>m}d1=nearPair(S1);d2=nearPair(S2);d=min(d1,d2,q-p);

returnd;}T(n)=2T(n/2)+O(n)=O(nlog2n)數(shù)據(jù)結(jié)構(gòu)與算法37貪心算法數(shù)據(jù)結(jié)構(gòu)與算法38貪心算法的概念

在解決某一問題的過程中，貪心算法總是做出在當(dāng)前看來最好的選擇。

也就是說，貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。（最終結(jié)果并不總是整體最優(yōu)）

貪心算法合理的稱謂：就急算法數(shù)據(jù)結(jié)構(gòu)與算法39四種硬幣

0.250.100.050.01

找顧客0.61

0.61-0.25=0.360.36-0.25=0.110.11-0.10=0.010.01-0.01=0.00整體最優(yōu)（幣數(shù)最少）本例的幣值結(jié)構(gòu)具有最優(yōu)子結(jié)構(gòu)性質(zhì)找錢問題數(shù)據(jù)結(jié)構(gòu)與算法40若四種硬幣

0.110.050.01

找顧客0.15

0.15-0.11=0.040.04-0.01=0.030.03-0.01=0.020.02-0.01=0.01一般可以得到整體近似最優(yōu)解0.01-0.01=0.000.15-3*0.05=0.00數(shù)據(jù)結(jié)構(gòu)與算法41貪心算法的設(shè)計模式Greedy(inputSet,Solution,target

){

Solution=?;target=?;

while(!findSolution){

x=select(inputSet);

iffeasible(Solution,x){

Solution=Solution∪x;change(target,x)}}

return

Solution;}數(shù)據(jù)結(jié)構(gòu)與算法42最小生成樹問題

(ST

G=(V,E))publicstaticvoidprim(intn,float[][]c){T=?;S={1};

while(S!=V){(i,j)=min(c[i][j])|i∈S&&j∈V-S

T=T

∪{(i,j)};

S=S

∪{j};}}數(shù)據(jù)結(jié)構(gòu)與算法43abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=

14+8+3+5+16+21

=67數(shù)據(jù)結(jié)構(gòu)與算法44回溯算法數(shù)據(jù)結(jié)構(gòu)與算法45數(shù)據(jù)結(jié)構(gòu)與算法46

回溯算法術(shù)語

1.解向量：問題解的向量表示形式。

(x1,x2,…,xk)kn,n:問題的規(guī)模。

2.約束條件

1）顯式約束：對分量xi的取值限定。

2）隱式約束：為滿足問題的解，不同分

量之間應(yīng)遵守的約束。

3.解空間：對于問題的一個實例，解向量滿足

顯式約束條件的所有多元組，構(gòu)成了該

實例的一個解空間。數(shù)據(jù)結(jié)構(gòu)與算法47

狀態(tài)空間樹

用于描述解空間的邏輯結(jié)構(gòu)樹

目標(biāo)函數(shù)與最優(yōu)解

1.目標(biāo)函數(shù)：衡量問題解

“優(yōu)劣”的標(biāo)準(zhǔn)

2.最優(yōu)解：使目標(biāo)函數(shù)取極