高级算法设计2011

高级算法设计计算机学院林永钢10/25/20231前言旅行商问题TravelingSalesmanProblem(TSP):

设有n个城市，已知任意两城市之间距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。穷举法的时间复杂性为O(n!)n=21时，21!=5.11×1019,设每条路径需CPU时间为1ns

，则总共要1620多年才能完成。10/25/20232前言Asurveyofalgorithmicdesigntechniques.Abstractthinking.Howtodevelopnewalgorithmsforanyproblemthatmayarise.Beagreatthinkeranddesigner.Not:Alistofalgorithms-Learntheircode-Implementthem-beamundaneprogrammer10/25/20233前言：学习算法的意义

Story-1

Seriousdamagetoyourpositionwithinthecompany!!!“Ican’tfindanefficientalgorithm,IguessI’mjusttoodumb.”10/25/20234前言：学习算法的意义

Story-2

“Ican’tfindanefficientalgorithm,becausenosuchalgorithmispossible!”Unfortunately,provingintractabilitycanbejustashardasfindingefficientalgorithms!!!

Nohope!!!P

NP10/25/20235前言：学习算法的意义

Story-3

“Ican’tfindanefficientalgorithm,butneithercanallthesefamouspeople”10/25/20236前言：学习算法的意义

Story-4

“Anyway,wehavetosolvethisproblem.Canwesatisfywithagoodsolution?“10/25/20237本课程教材及主要参考书[1](教材)（美）科曼(Cormen,T.H.）.潘金贵译.算法导论(IntroductiontoAlgorithmsSecondEdition)，机械工业出版社，2006.9[2]王晓东.计算机算法设计与分析，电子工业出版社，200610/25/20238课程内容分治法(矩阵计算等)、贪心法(最小生成树、单源最短路径问题等)、动态规划(每对顶点间的最短路径等)、搜索法、线性规划、网络流、数论、NP问题及近似算法等.10/25/20239

(1)

皇后问题:这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在n×n格的棋盘上如何能摆上n个皇后而使她们都不能互相攻击。

一些有趣的问题设n=4，试一试。当n很大时，问题很难。

对于n=8,现已知此问题

共有92种解，但只有12

种是独立的，其余的都

可以由这12种利用对称

或旋转而得到。10/25/202310(2)背包问题1：有一旅行者要从n种物品中选取不超过b千克重的行李随身携带，要求总价值最大。例：设背包的容量为50千克。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。求总价值最大。(3)背包问题2：有一商人要从n种货物中选取不超过b千克重的行李随身携带，要求总价值最大。例：设背包的容量为50千克。物品1有60千克，每千克价值60元；物品2有20千克，每千克价值100元；物品3有40千克，每千克价值120元。求总价值最大。10/25/202311有八种化学药品A、B、C、D、W、X、Y、Z要装箱运输。虽然量不大，仅装1箱也装不满，但出于安全考虑，有些药品不能同装一箱。在下表中，符号“×”表示相应的两种药品不能同装一箱。运输这八种化学药品至少需要装

箱。

前言（4）化学药品装箱10/25/20231210/25/202313前言（4）着色：北京地图10/25/202314着色问题就是对图G

的每个顶点指定一种颜色,使邻接的结点着不同的颜色.G

的着色数记为x(G)。结点着色10/25/202315韦尔奇

鲍威尔法(WelchPowell)1)将图G

中的结点按度数递减的次序进行排列(相同度数的结点的排列随意)。2)用第一种颜色，对第一点着色，并按排列次序对与前面结点不相邻的每一点着同样的颜色。3)用第二种颜色对尚未着色的点重复第2步,直到所有的点都着上颜色为止。10/25/202316例试用韦尔奇

鲍威尔法对图进行着色。按度数递减次序排列各点CABFGHDE第一种颜色：第二种颜色：第三种颜色:解：C,A,GB,H,D,EF所以图是三色的。另外图不能是两色的,因为图中有A,B,F两两相邻,所以x(G)=310/25/202317Y、X、D、A、B、C、W、Z10/25/202318前言（4）续已知研究生选课情况，安排课程考试的日程研究生选课情况表

姓名选修课1选修课2选修课3

杨一算法分析（A）形式语言（B）计算机网络（E）

石磊计算机图形学（C）模式识别（D）

魏涛计算机图形学（C）计算机网络（E）人工智能（F）

马耀先模式识别（D）人工智能（F）算法分析（A）

齐砚生形式语言（B）人工智能（F）10/25/202319

课程关系图DEFCBA顶点：表示课程；

姓名选修课1选修课2选修课3

杨一算法分析（A）形式语言（B）计算机网络（E）

石磊计算机图形学（C）模式识别（D）

魏涛计算机图形学（C）计算机网络（E）人工智能（F）

马耀先模式识别（D）人工智能（F）算法分析（A）

齐砚生形式语言（B）人工智能（F）边：同一研究生选修的课程用边连接----有边连接的课程不能按排在同一时间考试；10/25/202320◆课程考试按排问题转化为图的着色问题

--用尽可能少的颜色该图的每个顶点着色，使相邻的顶点着上不同的颜色；

---每一种颜色代表一个考试时间，着上相同颜色的顶点是可以安排在同一时间考试的课程；按顶点度数从大到小排列：FAECBD

F:蓝色

;A,C:红色；E,D:绿色；B:黄色；

即A,C可安排在同一时间考试，E,D可安排在同一时间考试;DEFCBAACEFBD10/25/202321绪言一、算法设计与分析的研究对象非数值问题二、什么是算法例1已知两正整数m和n，求二者的最大公因子算法1.1欧几里德(Euclid)算法输入正整数m,n输出m和n的最大公因子

10/25/202322定理对任意正整数m和任意非负整数n，并且m>n≥0

有gcd(m,n)=gcd(n,mmodn)

如gcd(24,18)=gcd(18,6)=gcd(6,0)=610/25/202323S1求余数:m除以n,令r是所得的余数，转S2S2判断余数:若r=0,则输出n的当前值，算法结束，否则转S3S3代替:m←n,n←r,转S110/25/202324算法的五个特征1）有穷性2）确定性3）输入4）输出5）可行性算法的定义:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

10/25/202325评价算法的标准1）算法执行的时间短（时间复杂性）2）算法需要的存储空间小（空间复杂性）3）正确性

4）可读性5）最优性10/25/202326算法的复杂性10/25/202327符号一、符号说明1．取整函数

x

：小于等于x的最大整数

x

：大于等于x的最小整数性质

x-1<x

x

x

<x+110/25/202328符号10/25/202329符号logb

N=loga

N/logablogeN=lnN

e=2.71828logab=1/logba10/25/202330符号二、求和等比级数的求和公式10/25/202331算法的时间复杂性：处理一个问题规模为n的输入，算法所需要的执行次数（或执行的步数），记为T(n)算法的空间复杂性：处理一个问题规模为n的输入，算法所需要的空间数，记为S(n)10/25/202332O、o、、、第一种理解方法设f和g是定义域为自然数N上的函数f(n)=O(g(n)).

若存在正数c和n0使得对一切n

n0

有0f(n)cg(n)f(n)=(g(n)).

若存在正数c和n0使得对一切n

n0有0cg(n)f(n)f(n)=o(g(n)).

若对任意正数c存在n0使得对一切n

n0有0f(n)<cg(n)f(n)=(g(n)).

若对任意正数c存在n0使得对一切n

n0有0cg(n)<f(n)f(n)=(g(n))

f(n)=O(g(n))且f(n)=(g(n))10/25/202333O、o、、、第二种理解方法求复杂性函数阶的极限方法例如，f(n)=n2/4,g(n)=n2,则n2/4=θ(n2)f(n)=lg

n,g(n)=n,则lg

n=o(n)o

10/25/202334f(n)c0g(n)c1g(n)n0f(n)is

(g(n))

f(n)cg(n)n0f(n)isO(g(n))

f(n)cg(n)n0f(n)is

(g(n))

10/25/202335例：60n2+5n+1

lim(60n2+5n+1)/n2=60所以

60n2+5n+1=Θ(n2)10/25/202336等式0.75n2=O(n)何时成立？永不成立等式3n1/2=O(n)在n=9时成立吗？n=9时，虽然两边值相等，但等式不成立10/25/202337例：1+2+…+n

1+2+…+n

≤n+n+…+n=n2

对于n

≥1

所以

1+2+…+n=O(n2)

又1+2+…+n

≥1+1+…+1=n

对于n

≥1

所以1+2+…+n=Ω(n)综上1+2+…+n=?10/25/202338方法：分割求和为方便起见,设n为偶数,则

10/25/202339所以1+2+…+n=Ω(n2)综上1+2+…+n=Θ(n2)练习：给出1k+2k+…+nk

的Θ表示

1k+2k+…+nk=Θ(nk+1)

10/25/202340标准复杂性函数的比较

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)注意：1）不能划等号2）以下若无特殊声明，log是以2为底的对数3）上式只有在n较大的时候成立O(1)的含义？计算时间由一个常数（零次多项式）来限界多项式时间阶指数时间阶10/25/202341指数时间一个算法的时间复杂性如果是O(2n)，则称此算法需要指数时间。多项式时间一个算法的时间复杂性如果是O(nk)(k为有理数），则称此算法需要多项式时间。有效算法以多项式时间为限界的算法称为有效算法。10/25/202342TimetoFinishInputSize(n)O(nx)O(n)O(1)O(n

lg

n)O(an)10/25/202343例例：算法A1,A2的时间复杂性分别是n,2n,设100μs是一个单位时间，求A1,A2在1s内能处理的问题规模。已知lg2=0.301T(n)=nT(n)*10-4=1即n*10-4=1所以n=

104

10/25/202344时间复杂性函数问题规模102030405060n10－52*10－53*10-54*10-55*10-56*10-5n210-44*10-49*10-416*10-425*10-436*10-4n310-38*10-327*10-364*10-3125*10-3216*10-3n510-13.224.31.7分5.2分13.0分2n.001秒1.0秒17.9分12.7天35.7年366世纪3n.059秒58分6.5年3855世纪2*108世纪1.3*1013世纪10/25/202345

时间复杂性函数1小时可解的问题实例的最大规模计算机快100倍的计算机快1000倍的计算机nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.2910/25/202346递归式及三种解法10/25/202347方法一:特征方程法10/25/202348斐波那契数递归方程及其求解定义：给定一个数的序列T(0),T(1),…,

T(n),…,把T(n)和某些T(i)(0≤i<n)联系起来的一个等式就叫做一个递归关系。如果一对大兔子每月能生一对小兔，而每对小兔在出生后的第三个月又能生一对小兔。问由一对小兔开始，n个月后将有多少对兔子？F(n)

=F(n–1)+F(n–2)F(1)

=1F(2)

=1为递归关系的初始条件。10/25/202349常系数线性齐次递归关系的求解定义设a1,a2,…ak是k个常数，且ak≠0，则递归关系

T(n)

=a1T(n–1)+a2T(n–2)

+…

+akT(n–k)

n≥k

称为k阶常系数线性齐次递归关系。

10/25/202350例求递归关系T(n)

=

5T(n–1)

–6T(n–2)

(n≥2)满足初始条件T(0)

=0,T(1)

=1的解一般的,都有T(n)

=xn解此递归关系的特征方程为x2–5x+6=0

即(x–2)(x–3)

=0，特征根为x1=2,x2=3因此递归关系的通解为T(n)

=A12n+A23n

特征方程无重根：如果递归关系的k个特征根q1,q2,…,qk互不相等，则

T(n)

=A1q1n+A2q2n+…+Akqkn是递归关系的通解。其中A1,A2,…Ak为任意常数。10/25/202351代入初始条件0=A120+A230=A1

+A2

1=A121+A231=2A1

+3A2

A1=-1A2=1因此递归关系的通解为T(n)

=-2n+3n递归关系T(n)

=

5T(n–1)

–6T(n–2)

(n≥2)初始条件T(0)

=0,T(1)

=1

特征方程为x2–5x+6=0

特征根为x1=2,x2=3递归关系的通解为T(n)

=A12n+A23n

10/25/202352斐波那契数F(n)

=F(n–1)+F(n–2)F(1)

=1F(2)

=1特征方程为x2–x–1=0

特征根为x1=,x2=

递归关系的通解为F(n)

=

代入初始条件

A1=A2=

因此通解为F(n)

=10/25/202353方法二:主定理法10/25/202354分治法10/25/202355基本思想：将问题分解成若干个子问题，然后求解子问题，由此得到原问题的解。即“分而治之”把输入分成与原问题类型相同的多个子问题10/25/202356问题分解子问题分解基本问题

求解基本问题解

合并子问题解

合并问题解10/25/202357分治法是一个递归地求解问题的过程分治法在每一层递归上有三个步骤分解:通过某种方法,将原问题分解成若干个规模较小,相互独立,与原问题形式相同的子问题解决:若子问题规模小到可以直接解决(称为基本问题),则直接解决,否则把子问题进一步分解，递归求解合并:通过某种方法,将子问题的解合并为原问题的解10/25/202358分治法的抽象过程divide-and-conquer(S){if(small(S))return(adhoc(S));divideSintosmallersubsetS1,S2,…,Si,…Sk;for(i=1;i<=k;i++)

yi

←divide-and-conquer(Si);returnmerge(y1,y2,…,yi,…,yk);}10/25/202359例1用分治法求n个元素集合S中的最大、最小元素。假设n=2m。要求每次平分成2个子集。voidmaxmin(int

A[],int&e_max,int&e_min,int

low,inthigh)2.{3.intmid,x1,y1,x2,y2;4.if((high-low<=1)){5.if(A[high]>A[low]){6.e_max=A[high];7.e_min=A[low];8.}特征1：

小到容易求解9.else{10.e_max=A[low];11.e_min=A[high];12.}13.}10/25/20236014.else{15.mid=(low+high)/2;16.maxmin(A,x1,y1,low,mid);17.maxmin(A,x2,y2,mid+1,high);18.e_max=max(x1,x2);19.e_min=min(y1,y2);20.}21.}特征2：

可分解特征4：

子问题独立特征3：

可合并T(n)=1n=2n>22T(n/2)+210/25/202361课堂练习用分治法求n个元素集合S中的最大、最小元素。写出算法，并分析时间复杂性（比较次数）。假设n=3m。要求每次平分成3个子集。T(n)=n=3n>33T(n/3)+4310/25/202362归并排序前言归并---合并两个有序的序列假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A和B的归并，其复杂度为bn，即O(n)。10/25/202363归并排序前言归并---合并两个有序的序列A:138911B:2571013C:1

2

3

5

7

8

9

10

11

1310/25/202364归并排序前言voidmerge(TA[],int

Alen,TB[],int

Blen,TC[]){

inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++];} while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}10/25/202365归并排序（MergeSort)归并排序是一个分治递归算法递归基础：若序列只有一个元素，则它是有序的，不执行任何操作递归步骤：先把序列划分成长度基本相等的两个序列对每个子序列递归排序把排好序的子序列归并成最后的结果10/25/202366归并排序（MergeSort)归并排序初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]归并：[4，8][5，6][1，2][3，7]归并：[4，5，6，8][1，2，3，7]归并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]10/25/202367归并排序（MergeSort)voidMergeSort(intA[],intB[],intl,inth){ if(l==h) return;

intm=(l+h)/2;

MergeSort(A,B,l,m);

MergeSort(A,B,m+1,h); Merge(A,B,l,m,h);}T(n)=n=2n>22T(n/2)

+cn110/25/202368方法三:主定理设a≥1和b>1为常数,设f(n)为函数,T(n)由递归式

T(n)

=

aT(n/b)

+f(n)

对自然数定义,其中n/b指

n/b

或

n/b

.则若对于某常数ε>0,有则T(n)

=

若

则T(n)

=

若对于某常数ε>0,有且对常数c<1与所有足够大的n,有

af(n/b)≤cf(n),则T(n)

=10/25/202369主定理简化版T(n)=n=2n>2aT(n/c)

+bnxdT(n)=a<cx

(nx

logn)

(nx)a=cxa>cxT(n)=n=2n>22T(n/2)

+cn1归并排序

(nlogn)T(n)=1n=2n>22T(n/2)+210/25/202370方法三:递归树法10/25/202371递归树:例1T(n)=n=2n>22T(n/2)

+cn

(1)10/25/202372递归树归并排序

(nlgn)T(n)=n=2n>22T(n/2)

+cn

(1)10/25/202373递归树:例2T(n)=3T(n/4)+cn2

10/25/202374递归树T(n)=3T(n/4)+cn2

10/25/202375递归树T(n)=3T(n/4)+cn2

10/25/202376二分法10/25/202377为什么要用二分法用枚举的方法求解，需要对所有解都遍历一次，时间复杂度为O(n)用二分法，每进行一次运算，能将解的范围缩小一半，时间复杂度为O(logn)10/25/202378使用二分法的条件解具有递增（或递减）的特性对于某个值不是问题的解，那么比这个值大（或小）的值均不是问题的解10/25/202379程序的一般形式While(min<max){ mid=(min+max)/2; if(与mid有关的条件) min=mid+1; elsemax=mid;}10/25/202380第一类问题求一个问题的解:连续、离散……10/25/202381第一类问题:求方程的解（2，3）（2.5，3）（2.5，2.75）（2.5，2.5625）（2.53125，2.5625）（2.53125，2.546875）2.52.752.6252.56252.531252.546875（2.5，2.625）2.5390625-0.0840.5120.2150.066-0.0090.0290.010(精确度为0.01)10/25/202382第一类问题:折半查找给定一个有序的数列，判断某个数是否在数列中161522274851556071minmaxmid10/25/202383二分查找法（也称为折半查找法）基本步骤：将给定值与查找范围中间位置的记录比较：

给定值＜中间位置：继续在前半个表中查找

=

：查找成功，返回记录位置

＞：继续在后半个表中查找10/25/202384L=(3,12,24,37,45,53,61,78,90,100)，查找Key=24的记录

12345678910

31224374553617890100lowmid

high

12345678910

3122437

4553617890100lowmidhigh

24＜

45继续在前半个表中用二分查找法查找

12345678910312

2437

4553617890100Lowmidhigh

24＞

12继续在后半个表中用二分查找法查找查找成功mid=(low+high)/210/25/202385第二类问题求一个问题的最优解：最大、最小……10/25/202386第二类问题:分割电缆现给出4根电缆，长度分别为8.02、7.43、

4.57、

5.39，要你把它们分割成11根等长的电缆，每根电缆的最大长度是多少？10/25/202387大整数乘法在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。10/25/202388普通递归乘法的分析设X,Y是n位二进制整数，分段表示如下：即X=A2n/2+B,Y=C2n/2+D

则XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD计算成本：4次n/2位乘法，3次不超过n位加法，2次移位，所有加法和移位共计O(n)次运算。我们有T(n)=O(n2)

1n=14T(n/2)+O(n)n>1T(n)=10/25/202389改进的分治算法(1962年)

由X=A2n/2+B,Y=C2n/2+D则

XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD=AC2n+((A-B)(D-C)+AC+BD)2n/2+BD计算成本：3次n/2位乘法，6次不超过n位加减法，2次移位，所有加法和移位共计O(n)次运算。由此可得，T(n)=O(nlog3)=O(n1.59)这种思想同样可以用于十进制数的乘法中。

1n=13T(n/2)+cnn>1T(n)=10/25/202390改进的分治算法举例：十进制数的乘法已知X=2368，y=3925，求XY解：取基d=10,A=23,B=68,C=39,D=25,则①AC=23×39=897②BD=68×25=1700③(A-B)(D-C)+AC+BD=(23-68)(25-39)+897+1700=45×14＋897＋1700=3227

∴XY=1700+3227×102＋897×104＝929440010/25/202391Strassen矩阵乘法普通矩阵乘法设n×n阶矩阵A和B，计算C=A×B求C=AB即对n2个元素cij进行计算，故要作n3次乘法。相当长时间内没有人怀疑过是否可以用少于n3次乘法来完成。10/25/202392以n=2为例的普通矩阵乘法设则有共需8次乘法10/25/202393-将C=A×B写为2×2的分块矩阵：-Strassen提出的算法如下：令P=(A11+A22)(B11+B22),Q=(A21+A22)B11R=A11(B12-B22),S=A22(B21-B11)T=(A11+A12)B22,U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)

则

C11=P+S-T+V,C12=R+TC21=Q+S,C22=P+R-Q+U

乘法次数从8次减为7次。Strassen的分治算法(1969)10/25/202394时间分析：用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程:=>T(n)=O(nlog7)≈O(n2.81)10/25/202395快排序:介绍快速排序算法是于1962年由英国的TonyHoare提出的，并于1980年获得TuringAwards最坏运行时间:(n2)平均运行时间:(nlogn)－实际运行效果最好的排序算法－在(nlogn)中的常数因子非常小10/25/202396快排序（QuickSort)快排序—算法思想取序列的一个元素作为轴，利用这个轴把序列分成三段：左段，中段(轴),和右段,使左段中各元素都小于等于轴，右段中各元素都大于等于轴。(这个过程称做对序列的划分)左段和右段的元素可以独立排序,将排好序的三段合并到一起即可上面的过程可以递归地执行，直到每段的长度为110/25/202397快排序—算法思想快速排序实例10/25/202398快排序---划分过程快排序是一个分治算法快排序的关键过程是每次递归的划分过程划分问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边10/25/202399划分算法：用临时变量对轴备份取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high移动两个指针首先从high所指的位置向左搜索，找到第一个小于轴的元素,把这个元素放在low的位置再从low开始向右，找到第一个大于轴的元素，把它放在high的位置重复上述过程，直到low=high，把轴放在low所指的位置10/25/2023100快排序---划分过程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low10/25/2023101算法分析最坏情况：12345671

23456712

3456712

34567当需要排序的序列已经有序时，快排序需要做n-1次划分，每次划分需要的比较次数依次为n-1,n-2,…,1.所以在这种情况下，快排序的时间复杂度为10/25/2023102最好情况如果每次划分过程产生的区间大小都为n/2，这时有：T(n)=2T(n/2)+θ(n)

T(1)=0nn/2n/2n/4n/4n/4n/4n/8n/8n/8n/8n/8n/8n/8n/8log2nnBestCaseComplexity

nlognT(n)=O(nlogn)a=c10/25/2023103算法优化

轴的选择基本快排序算法选择序列的第一个元素为轴，当轴使每次划分后的两个子序列长度接近时，算法效率很高，如果偏向某一边，则效率偏低为了打破极端偏向某一边，可以用其他策略选择轴在序列中随机选择一个元素作为轴选择Array[0],Array[n-1],Array[(n-1)/2]三个数

的中间值作为轴10/25/2023104算法优化短序列排序：快排序对序列长度较大时很有效，但当序列较短时则效率不高，因为快排序是个递归算法，需要大量子过程调用可以做如下改进：当序列长度较大时采用快排序算法。当序列长度被划分到小到一定长度时，采用较直接的算法（如插入排序）10/25/2023105快排序（QuickSort)算法评论：对很长的序列来说，快速排序的平均性能最好。因此在很多软件，比如数据库系统中经常使用10/25/2023106线性时间选择问题:用线性时间从n个不同的元素中选择出第k个小的元素10/25/2023107笔试题在中国的古代，25匹马通过赛跑来决出前3名，每5匹马一组，问最少需要几组？5组从快到慢ABCDEDCAEB由快到慢10/25/2023108求第k小的元素算法的基本思想按某个元素m将S中的元素划分成小于m、等于m和大于m的三个子序列S1，S2和S3。

只要计算一下这三个集合的元素个数，就能确定第k小元素在哪个子集中。这样就把在S中找第k小元素的问题转化成在S的某个子集中找某个元素的问题。递归地运用这一方法，就可找出S中第k小元素。10/25/2023109求第k小的元素longSelect(k,S){if(|S|≤38){将S中的元素排成非递减序；

return(S中的第k小元素);}else

{

将S中的元素划分成长度等于5的

|S|/5

个子序列；10/25/2023110由各子序列的中值元素组成非递减序列M；

m←Select(

|M|/2

，M);

按m将S中的元素划分成小于m、等于

m和大于m的三个子序列S1，S2和S3;if(|S1|≥k)return(Select(k,S1));elseif(|S1|+|S2|≥k)return(m);elsereturn(Select(k-|S1|-|S2|,S3));}}10/25/2023111求第k个小的元素（选择问题）m中值序列M

从小到大已知小于或者等于m的元素已知大于或者等于m的元素按m将S中的元素划分成小于m、等于m和大于m的三个子序列S1，S2和S3;从小到大10/25/2023112定理：算法Select在O(n)时间内找出n个元素序列中的第k小的元素。

cn≤38T(

n/5

)+T(

3n/4

)+cnn>38T(n)≤T(n)=O(n)10/25/2023113选择问题的应用之一用选择算法找中位数作为划分标准，保证快速排序算法的子问题均衡,使得快速排序算法最坏情况复杂性为O(nlogn)。10/25/2023114线性时间选择:中位数引例某公司有五个分公司依次设置在同一条铁路线的沿线A、B、C、D、E站。现在该公司希望在该铁路沿线设立一个仓库，要求该仓库离这五个站的火车行驶距离之和最小。如用数轴表示该铁路线，A、B、C、D、E各站的坐标依次为a、b、c、d、e（a<b<c<d<e），则经过数学计算，该仓库大致应设置在坐标（1）处。（1）A.cB.(a+b+c+d+e)/5C.(a+2b+3c+2d+e)/9

D.(a+4b+6c+4d+e)/1610/25/2023115线性时间选择:中位数应用中位数原理X轴上有n个点，由左至右依次排列为找一个点xp(不一定是n个点之一)，使xp到各点距离和最小，解为：x1x2xpxnx即解为中位数或中位数的平均值。10/25/2023116线性时间选择:中位数应用主油管道最优位置问题主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。10/25/2023117线性时间选择:中位数应用问题分析－设n口油井的坐标(xi,yi)i=1,…,n，主管道的y坐标为yk。－显然，问题只要求y坐标的中位数即可。注：如果用排序方法，则T(n)=O(nlogn)

达不到线性时间要求。10/25/2023118【例】残缺棋盘残缺棋盘是一个有2k×2k

（k≥1）个方格的棋盘，其中恰有一个方格残缺。图中给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

①号②号③号④号

称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。10/25/2023119在此覆盖中要求：1）两个三格板不能重叠2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格10/25/2023120问题分解过程：以k=2时的问题为例，用二分法进行分解，得到如下图，用双线划分的四个k=1的棋盘。①号②号③号④号10/25/202312110/25/2023122循环赛日程表设计一个满足以下要求的比赛日程表（2k个选手）：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。10/25/2023123循环赛日程表加4加2(a)2k(k=1)个选手比赛122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)个选手比赛(c)2k(k=3)个选手比赛10/25/2023124循环赛日程表123456782143658734127856432187655678123465872143785634128765432110/25/2023125循环赛日程表的推广设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)n为偶数时，循环赛一共进行n-1天。

n为奇数时，循环赛一共进行n天。1234第1天第2天第3天10/25/20231261234第1天第2天第3天123第1天第2天第3天10/25/2023127123第1天21-第2天3-1第3天-32123456第1天第2天第3天第4天第5天10/25/202312812345第1天21-54第2天351-2第3天4321-第4天5-431第5天-452310/25/202312912345678910第1天21854763109第2天35192810647第3天43211098765第4天57431102986第5天64523191078第6天78910651234第7天89106745123第8天91067834512第9天1067892345110/25/2023130课堂练习

甲手中有1张A，2张2，3张3，4张4，5张5，6张6，7张7，8张8，9张9共45张牌，现甲从中任取一张牌，然后乙开始提问来猜出这张牌。请给出乙提问的平均最少次数。10/25/2023131贪心法（贪婪法）

10/25/2023132数钱

一出纳员支付一定数量的现金。假设他手

中有各种面值的纸币和硬币，要求他用最

少的货币数支付规定的现金。

例如，现有4种硬币：它们的面值分别为1

分、2分、5分和1角。要支付2角5分。首先支付2个1角硬币，然后支付一个5分

硬币，这就是贪心策略。10/25/2023133贪心法不一定能产生正确的答案。例如，若引进一个1角1分的硬币，设从如下集合{1,1,2,2,2,5,10,10,11,11}中数出25分，按贪心法，共4个硬币。但最优解仅为3个硬币。这说明贪心法得到的解只是一个可行解。10/25/2023134夜晚过一桥，甲过需要一分钟，乙两分钟，丙五分钟，丁十分钟。桥一次最多只能承受两人，过桥必须使用手电筒，现在只有一只手电筒。请问4人最少用多少时间全部过桥？10/25/2023135一、Huffman编码

某通讯系统只使用5种字符a、b、c、d、e，使用频率分别为0.1,0.14,0.2,0.26,0.3,利用二叉树设计不等长编码：1）构造以a、b、c、d、e为叶子的二叉树；2）将该二叉树所有左分枝标记0，所有右

分枝标记1；3）从根到叶子路径上标记作为叶子结点所

对应字符的编码；10/25/2023136

acbdea:000b:001c:01d:10e:115种字符a、b、c、d、e，使用频率分别为0.1,0.14,0.2,0.26,0.330000-(1000+1400)*3-(2000+2600+3000)*2=760010/25/2023137二、货郎担（TSP）问题

设售货员要到五个城市去售货，最后再回到出发的城市。已知从一个城市到其他城市的费用，求总费用最少的路线10/25/2023138权为13从不同结点出发：

1）结点a为起点：

2）结点b为起点：

3）结点c为起点：

4）结点d为起点：权为13权为13权为13abcd213743或者1510/25/2023139而实际上图中最短哈密顿

回路的长度为12。即abcdaabcd21374310/25/2023140背包问题已知一个容量大小为M重量的背包和n种物品，物品i的重量为wi,假定物品i的一部分xi放入背包会得到vixi这么大的收益，这里，0≤xi≤1，vi>0。采用怎样的装包方法才会使装入背包的物品总效益最大？例：考虑以下情况下的背包问题

n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)10/25/2023141n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

1)按效益值非增次序将物品依次放入背包

(x1,x2,x3)Σwixi

Σvixi2)按物品重量的非降次序将物品依次放入背包(1,2/15,0)2028.2(0,2/3,1)203110/25/2023142n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

3)按vi/wi的非增次序将物品依次放入背包

(x1,x2,x3)Σwixi

Σvixi

(0,1,1/2)2031.5算法：背包问题的贪心算法10/25/2023143voidGreedyKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//使v1/w1≥v2/w2≥…≥vn/wn

for(inti=1;i<=n;i++)x[i]=0;floatc=M;

for(inti=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}10/25/2023144算法的时间复杂性为

O(nlogn)下面来证明使用此贪心算法所得到的贪

心解是一个最优解。证明的基本思想是：把这个贪心解与任一个最优解相比较，如

果这两个解不同，就去找开始不同的第一

个xi，然后设法用贪心解的这个xi去代换最优解的那个xi，并证明在分量作了代换10/25/2023145之后其总效益与代换之前无任何损失。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解是最优解。定理：如果v1/w1

≥v2/w2

≥···

≥

vn/wn,

则此算法对于给定的背包问题实例生成一

个最优解。10/25/202314610/25/202314710/25/2023148例：某公司新建一座200平米的厂房，现准备部署生产某产品的设备。该公司现空闲生产该产品的甲、乙、丙、丁四种型号的设备各3台，每种型号设备每天的生产能力由下表给出。在厂房大小限定的情况下，该厂房每天最多能生产该产品（

）个。10/25/2023149活动安排:问题描述有n个活动集E={1,2,…,n}使用同一资源，而同一时间内同一资源只能由一个活动使用。每个活动的使用时间为[si,fi)i=1,…,n，si为开始时间，fi为结束时间，若[si,fi)与[sj,fj)不相交称活动i和活动j是相容的。问题：选出最大的相容活动子集合。10/25/2023150贪心策略将各活动按结束时间排序f1≤f2≤…≤fn，先选出活动1，然后按活动编好从小到大的次序依次选择与当前活动相容的活动。注：这种策略使剩余的可安排时间极大化，以便于安排尽可能多的相容活动。10/25/2023151活动安排:计算示例11个活动已按结束时间排序，用贪心算法求解：

i1234567891011start_timei

130535688212finish_timei

456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活动：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a1110/25/2023152有限期的任务安排问题用贪心法求解有限期的任务安排问题：假设只能在同一台机器上加工n个任务，每个任务i完成时间均是一个单位时间。又设每个任务i都有一个完成期限di>0,当且仅当任务i在它的期限截止以前被完成时，任务i才能获得pi的效益，每个任务的期限从整个工序的开工开始计时，问应如何安排加工顺序，才能获得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2)10/25/2023153有限期的任务安排问题

首先按效益非增次序进行排序，然后按照

期限依次对此次序进行调整，排在后面的

或提前或排除。10/25/2023154假设n个任务已按p1≥p2≥···

≥

pn

排序。首先将任务1存入解数组J中，然后处理任务2到任务n。假设已处理了i-1个任务,其中有k个任务已记入J(1),J(2),···,J(k)之中，并且有d(J(1))≤d(J(2))≤···≤d(J(k))。现在处理任务i。为了判断J∪{i}是否可行，只需看能否找出这样的位置：可以按期限的非降次序插入任务i，使得i在此处插入后，有d(J(r))≥r,1≤r≤k+1。10/25/2023155找任务i可能的插入位置可如下进行：（a）若d(i)>d(J(k)),即任务i的期限比这k个任务的所有期限都长，则i可直接加入到k个任务的后面，即J(k+1)=i（b）将d(J(k)),d(J(k-1)),···,d(J(1))逐个与d(i)比较,直到找到位置q，它使得①d(J(q))≤d(i)<d(J(t))q<t≤k10/25/2023156此时若②d(J(t))>tq<t≤k这说明：第t个要加工