北京工业大学：数据结构与算法分析 教学课件第十章 算法设计与分析导论

数据结构与C/C++&Java北京工业大学计算机学院软件学科部陈文博

2004数据结构与算法1第十章算法设计与分析导论数据结构与算法2主要内容

算法设计与分析内容介绍算法分析的方法递归与分治算法回溯算法贪心算法

数据结构与算法3算法设计与分析内容介绍从引例看算法设计表达算法的抽象机制数学算法与数据结构算法算法与数据结构的关系算法分析的方法常用算法模式数据结构与算法4010203040506071234四染色地理结论的实现123456712345670111111100011010011001010100111101111001011000110从引例看算法设计11数据结构与算法5BacktrackingAlgorithmIdea数据结构与算法6publicbooleanbacktrack(){

Stack

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

i

isnumberofatask

j=1;//the

j

isitemnumberofchoice

do{

}(!wholeprojecthascompleted)}//accomplishbacktrack数据结构与算法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)数据结构与算法8

ADT

Stack

{

数据对象：

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

数据关系：

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

约定an

端为栈顶，a1端为栈底。

}ADTStack

基本操作：

Stack()

empty()

push(e)

pop()数据结构与算法9表达算法的抽象机制数

据

模

型初始状态结果状态算

法顶层算法底层算法宏观步骤

算法骨干变量抽象

运算粗化微观步骤

算法细节变量具体

运算细化ADT(抽象)运算步骤数据结构与算法10数学层面的算法与数据结构层面的算法数据结构层面的算法publicObjectpop(){

if(empty())

thrownewEmptyStackException();

ObjecttopElement=stack[top];

returntopElement;}涉及对具体数据结构的操作数据结构与算法11数学层面的算法不涉及对具体数据结构的操作只使用数据结构ADT的接口数据结构与算法12算法与数据结构的关系算法vs

抽象的逻辑的数据结构四染色算法vs

具体的数据结构四染色算法vs

逻辑的数据结构

（往往由控制结构得到体现）whileifelseifdo数据结构与算法13算法分析的方法

渐进时间复杂度平均时间复杂度

一般的分析方法递归方程的求解数据结构与算法14四染色算法的分析例四染色回溯算法4*4*4……4n=4nT(n)=O(4n)数据结构与算法15voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。

if(n==1)move(x,1,z);//将编号为１的圆盘从x移到z

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

//将x上编号为１至n-1的圆盘移到y,z作辅助塔

move(x,n,z);

//将编号为n的圆盘从x移到zhanoi(n-1,y,x,z);

//将y上编号为１至n-1的圆盘移到z,x作辅助塔

}}Hanoi塔算法的分析数据结构与算法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)递归方程的求解数据结构与算法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)数据结构与算法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)

数据结构与算法19常用算法模式递归与分治算法动态规划贪心算法回溯算法分支限界算法概率算法遗传算法数据结构与算法20递归算法数据结构与算法21

后置递归法(Postponingthework)的设计思想为:假如某个问题的求解过程可以分成若干步进行，并且当前这一步的解可以直接求得，则先求出当前这一步的解，对于余下的问题，若问题的性质和原问题类似，则又可递归求解。

数据结构与算法22递归的终结状态是，当前的问题可以直接求解，对原问题而言，则是已走到了求解的最后一步。

链表是可以如此求解的一个典型例子。例如:编写“删除单链表中所有值为x

的数据元素”的算法。数据结构与算法23

1)单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素;分析:

2)从另一角度看，链表又是一个递归结构，若

L

是线性链表

(a1,a2,,an)

的头指针，则

L->next是线性链表

(a2,,an)的头指针。数据结构与算法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数据结构与算法25void

delete_L(LinkList&L,ElemTypex){

//删除以L为头指针的带头结点的单链表中

//所有值为x的数据元素

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数据结构与算法26void

delete_L(LinkList&L,ElemTypex){

//L为无头结点的单链表的头指针

if(L){

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

else

delete_L(L->next,x);}}4.递归函数中的尾递归容易消除。数据结构与算法27voiddelete(LinkList&L,ElemTypex){

//L为带头结点的单链表的头指针

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;}}}上述递归算法可改写为迭代的形式数据结构与算法28递归与分治算法数据结构与算法29

若求解问题的规模为n

其次，逐步合并子问题的解，直到获得原问题的解。

首先，把问题分解为k个性质相同、但规模

较小的子问题（1kn)，并求解这些子问题。（如果这些子问题的规模还不够“小”

，则可以进一步分解，直到可以求解为止）

分治法的概念数据结构与算法30PP1P2Pk……T1(n)T2(n)Tk(n)T(n)时间复杂度：T(n)=T1(n)+T2(n)+……+Tk(n)+C(n)

C(n)数据结构与算法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例归并排序数据结构与算法32T(n)T(n/2)T(n/2)Cn数据结构与算法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)数据结构与算法34分治算法的设计模式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);}数据结构与算法35最接近点对问题分析（直线上n个点，假设只有一对符合条件）算出每两个点的距离.若排序,需O(n2),希望O(nlog2n)mS1S2p1p2p3q3q1q2d=min{|p1-p2|,|q1-q2|}数据结构与算法36publicstaticdoublenearPair(S){n=|S|;

if(n<2)return;m=S中各点坐标的中位数；

构造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)数据结构与算法37贪心算法数据结构与算法38贪心算法的概念

在解决某一问题的过程中，贪心算法总是做出在当前看来最好的选择。

也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。（最终结果并不总是整体最优）

贪心算法合理的称谓：就急算法数据结构与算法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整体最优（币数最少）本例的币值结构具有最优子结构性质找钱问题数据结构与算法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一般可以得到整体近似最优解0.01-0.01=0.000.15-3*0.05=0.00数据结构与算法41贪心算法的设计模式Greedy(inputSet,Solution,target

){

Solution=Ø;target=Ø;

while(!findSolution){

x=select(inputSet);

iffeasible(Solution,x){

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

return

Solution;}数据结构与算法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};}}数据结构与算法43abcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和=

14+8+3+5+16+21

=67数据结构与算法44回溯算法数据结构与算法45数据结构与算法46

回溯算法术语

1.解向量：问题解的向量表示形式。

(x1,x2,…,xk)kn,n:问题的规模。

2.约束条件

1）显式约束：对分量xi的取值限定。

2）隐式约束：为满足问题的解，不同分

量之间应遵守的约束。

3.解空间：对于问题的一个实例，解向量满足

显式约束条件的所有多元组，构成了该

实例的一个解空间。数据结构与算法47

状态空间树

用于描述解空间的逻辑结构树

目标函数与最优解

1.目标函数：衡量问题解

“优劣”的标准

2.最优解：使目标函数取极