模版Word文档下载推荐.docx

模版Word文档下载推荐.docx

《模版Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《模版Word文档下载推荐.docx（18页珍藏版）》请在冰点文库上搜索。

2.指数量级时间的算法对于较大的n无实用价值。

什么是常系数线性递归方程（差分方程）？

c0an+c1an-1+…+cran-r=f（n）（*）（这里c0*cr≠0），所有ai都是一次的。

主定理的内容是什么？

根据主定理的结论，可以获得哪些关于算法改进的启示？

T（n）=a*T（n/b）+f（n）

若有ε>

0,使f（n）=O（

）（即f（n）的量级多项式地小于

的量级）,

则T（n）=（

）。

若f（n）=（

）（即f（n）的量级等于

则T（n）=（

）,则T（n）=（

0,使f（n）=（

）（即f（n）的量级多项式地大于

且满足正规性条件：

存在常数c<

1,使得对所有足够大的n，有a*f（n/b）c*f（n）,则T（n）=（f（n））。

正规性条件的直观含义:

对所有足够大的n，a个子问题的分解准备与再综合所需要的时间总和，严格小于原问题的分解准备和综合所需要的时间。

因此一般来说，对于时间复杂度满足递归关系T（n）=a*T（n/b）+f（n）的算法，只需比较f（n）与的量级大小，aLogbn算法的时间复杂度总是与量级大的那个相同（即小的那个可以忽略）；

若f（n）与的量级相同（或只差），aLogbnnLogk则算法的时间复杂度为f（n）*。

主定理对于算法改进得启示在于：

1）当T（n）=Θ（）时，即当的量级高于f（n）的量级时，n的量级在算法的时间复杂度中起主导作用。

因而此时首先应当考虑使aLogbnaLogbnaLogblogba的值变小，而暂时无须考虑如何改善f（n），即此时要考虑减小a（子问题个数）且使b不变（n/b为子问题规模），或增大b（减小子问题规模）而使a不变。

也就是说，此时的重点应考虑改进子问题的分解方法，暂不必考虑改进子问题组合时的处理。

2）当f（n）的量级高于或等于的量级时，则f（n）的量级在算法的时间复杂度中起主导作用。

因而此时首先应当考虑把f（n）的量级往下降，即此时应着重改善子问题组合时的处理方法，减少该部分工作的处理时间f（n）。

分治法的要领是什么？

（分治法可分为哪三个主要步骤？

）

分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；

首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。

由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。

因此分治法分三步：

1将原问题分解为子问题（Divide）。

2求解子问题（Conquer）。

3组合子问题的解得到原问题的解（Combine）。

分治法求最大、最小元算法的主要思路是什么？

当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。

当n>

2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。

先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；

将两个最小元进行比较，就可得n个元素的最小元。

叙述Strassen矩阵相乘算法的主要思路和意义。

把矩阵A，B分成4个规模为n/2的子矩阵块如下。

由于

＝

，所以，C11=A11B11+A12B21，C12=A11B12+A12B22，C21=A21B11+A22B21，C22=A21B12+A22B22。

同时引入下列Mi（i=1,2...7）M1=（A12-A22）（B21+B22），M2=（A11+A22）（B11+B12）

M3=（A11-A21）（B11+B12），M4=（A11+A12）B22，M5=A11（B12-B22），M6=A22（B21-B11）

M7=（A21+A22）B11则计算两个n阶矩阵的乘法为7对n/2阶矩阵的乘法（时间为7T（n/2））,18对n/2阶的矩阵的加减法（时间为18*（n/2）2=（n2））。

因此得时间复杂度的递归方程：

T（n）=7T（n/2）+（n2）,由主定理得T（n）=（

）.Strassen矩阵相乘算法意义在于打破了人们认为矩阵乘法的时间复杂度为（n3）的固有看法。

11．用200字概括Select（求第k小元）算法的主要思路。

1.若S<

50，则采用堆排序的方法找出第k小的元素。

若S50，则采用下述的方法。

2.将n个元素分成[n/5]组，每组5个元素

3.对每个5元组进行排序，全部5元组排序后，从每组中取出第3个元素（中间元）得到一个长为[n/5]的数组M

4.递归调用Select（[|M|/2],M），即在M数组中找到第[|M|/2]小的数（中位数），记为m

5.依次扫描整个数组S，此项工作所需时间为O（n）。

当si<

m时将si放入数组S1；

当si=m时将si放入数组S2；

当si>

m时将si放入数组S3；

在得到的3个集合中，S1中的数均小于m；

S2中的数均等于m；

S3中的数均大于m。

6.按照k值大小，共可分成下列三种情况（注意S2至少有一个元素m）：

k≤|S1|；

|S1|<

k≤|S1|+|S2|；

以及k>

|S1|+|S2|。

下面针对这三种情况分别进行讨论。

6.a：

若k≤|S1|，则第k小元素必定在S1中。

此时递归调用Select（k,S1），就可以获得第k小元素。

因大于等于m的数据元素至少有3n/10-6个，而S1中的数均小于m，故S1中的数据元素至多有7n/10+6个，即|S1|≤7n/10+6。

因此，调用Select（k,S1）的时间复杂度不超过T（7n/10+6）。

6.b：

若|S1|<

k≤|S1|+|S2|，则第k小元素必定在S2中。

因为S2中的元素的值均等于m，故第k小元素就是m。

由于答案已经得到，此时立刻返回第k小元素m。

这部分工作的时间复杂度为O

（1）。

6.c：

若k>

|S1|+|S2|，则第k小元素必定大于m，因此在S3中。

而且此时该元素在S3中应为第k-|S1|-|S2|小的元素。

于是递归调用Select（k-|S1|-|S2|,S3），就可以获得S中的第k小元素。

因小于等于m的数据元素至少有3n/10-6个

12.试用200～300字概述寻找最近点对算法的主要步骤。

该算法中有哪几点最为关键？

主程序算法：

读入n个点的坐标，这n个点的x坐标和y坐标分别放在X，Y两个数组中，然后进行预处理：

对X数组中的n个x坐标值按从小到大的次序进行排序，排序过程中保持x坐标和y坐标的对应关系：

若X[i]与X[j]对换位置，则Y[i]与Y[j]也做相同的对换。

另外，若两个点的x坐标相同，则y坐标值小的排前。

X数组排好之后就固定了，以后不再改变，以便在O

（1）时间对其实现分拆。

（排序时间为Θ（nlogn））将数组IND初始化为：

IND[i]=i（i=1,2,┉,n）。

数组IND即是用来保持x坐标和y坐标的对应关系的机制，IND[i]记录的是其y坐标值为Y[i]的点所对应的x坐标在X数组中的下标。

对Y数组中的n个y坐标值按从小到大的次序进行排序，排序过程中保持y坐标和x坐标的对应关系：

若Y[i]与Y[j]对换位置，则IND[i]与IND[j]也做相同的对换。

这样，当给了一个点的y坐标Y[i]之后，就可以在O

（1）时间找到其对应的x坐标：

Y[i]与X[IND[i]]就是该点的y坐标和x坐标。

调用子程序FCPP（1,n,X,Y,IND,δ,p,q）就可求得n个点中的最近点对（p,q）和最小距离δ。

子程序FCPP的主要执行过程：

首先看当前处理的点数。

若不超过3个点，就直接进行相互比较。

若超过3个点，则把点的y坐标分为两部分：

左边和右边。

然后进行分治，求得两边的δL和δR，从而求得δ。

求出分割线，扫描当前的所有点，把落到2δ带状区域内的点找出来，并使这些点的y坐标仍然保持从小到大的次序。

对落到2δ带状区域内的每一个点检查其后面的7个点，若有距离更近的点对，则把最小距离δ（及最近点对（p,q））更新，执行完毕时，最小距离δ及最近点对（p,q）就得到了。

子程序FCPP（j,k,X,Ypres,INDpres,δ,p,q）中的参数说明：

X数组存放已排好序的n个点的x坐标。

j,k为当前处理的X数组一段中的最小和最大下标。

Ypres数组存放当前处理的k-j+1个点的y坐标（已按从小到大的次序排好）。

INDpres数组的长度也是k-j+1，INDpres[i]记录了其y坐标值为Ypres[i]的点的x坐标在X数组中的下标值。

δ,p,q均为返回值，给出当前处理的k-j+1个点中的最小距离δ和最近点对（p,q）。

算法中的几个关键点：

分割线的寻找和最小距离相关的比较次数的判定

13.什么是离散傅立叶变换（DFT）？

其使用的矩阵有什么特点？

是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。

在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。

即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。

在实际应用中通常采用快速傅里叶变换以高效计算DFT。

14.什么是快速傅立叶变换（FFT）？

如何用FFT来计算2个多项式的乘积？

答:

能在Θ（nlogn）时间里完成DFT的算法就称为FFT.给了2个多项式的系数向量a和b之后，若其系数不是2的幂次，则将a和b的规模扩大（向量最后加若干个0）使得n=2m..然后把这两个向量维数再扩大一倍，得到两个维数为2n的向量。

分别对2个向量做DFT，所得到两个向量进行点乘，再对结果做2n阶的DFT-1,即可求得2多项式相乘后的多项式系数c

15.什么是平衡？

分治法与平衡之间有着什么样的关系？

在使用分治法和递归时，要尽量把问题分成规模相等，或至少是规模相近的子问题，这样才能提高算法的效率。

使子问题规模尽量接近的做法，就是所谓的平衡。

16.分治法与动态规划法之间的相同点是什么？

不同之处在哪些方面？

与分治法类似，动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。

动态规划法与分治法的一个重要的不同点在于，用分治法分解后得到的子问题通常都是相互独立的，而用动态规划法分解后得到的子问题很多都是重复的。

因此，对重复出现的子问题，只是在第一次遇到时才进行计算，然后把计算所得的结果保存起来；

当再次遇到该子问题时，就直接引用已保存的结果，而不再重新求解。

17.简述求矩阵连乘最少乘法次数的动态规划算法（不超过300字）

按照做最后一次乘法的位置进行划分，

该矩阵连乘一共可分为j-i种情况即有（j-i）种断开方式：

Mi（Mi+1┅Mj），（MiMi+1）（Mi+2┅Mj），┅，（MiMi+1┅Mj-1）Mj。

其中任一对括号内的矩阵个数（即规模）不超过j-i。

由于在此之前我们已知任一个规模不超过j-i的矩阵连乘所需的最少乘法次数，故（Mi┅Mk）和（Mk+1┅Mj）所需的最少乘法次数已知，将它们分别记之为mik和mk+1,j。

于是，形为（Mi⋯Mk）（Mk+1⋯Mj）的矩阵连乘所需的最少乘法次数为：

mik+mk+1,j+ri-1×

rk×

rj。

此式中的所有参加运算的数均已知，故此式在O

（1）时间里即可完成计算。

对满足i≤k<

j的共j-i种情况逐一进行比较，我们就可以得到矩阵连乘MiMi+1┅Mj-1Mj（i<

j）所需的最少乘法次数mij为：

mij=min（i≤k<

j）{mik+mk+1,j+ri-1×

rj}，（*）其计算可在O（j-i）时间里完成。

于是在初始时我们定义mii=0（相当于单个矩阵的情况），然后首先求出计算M1M2,M2M3,┅,Mn-1Mn所需的乘法次数mi,i+1（i=1,2,┅,n-1）,具体数值为ri-1×

ri×

ri+1,因mii=mi+1,i+1=0；

再利用这些结果和（*）式，就可以求出计算M1M2M3,M2M3M4,┅,Mn-2Mn-1Mn所需的最少乘法次数mi,i+2（i=1,2,┅,n-2）。

同理，可依次算出mi,i+3（i=1,2,┅,n-3），mi,i+4（i=1,2,┅,n-4），┅，直至算出m1,n即M1M2┅Mn-1Mn矩阵连乘所需的最少乘法次数。

18.能够用动态规划法求解的问题通常具有什么样的特征？

若一个问题可以分解为若干个高度重复的子问题，且问题也具有最优子结构性质，就可以用动态规划法求解：

以递推的方式逐层计算最优值并记录必要的信息，最后根据记录的信息构造最优解。

19.什么是最长公共子序列问题？

在求LCS的算法中，C[i,j]是如何计算的？

为什么需要这样计算？

若Z<

X，Z<

Y，且不存在比Z更长的X和Y的公共子序列，

则称Z是X和Y的最长公共子序列，记为Z∈LCS（X,Y）。

如何在低于指数级的时间复杂度内找到LCS称为最长公共子序列问题

C[i,j]=0,若i=0或j=0

C[I,j]=C[i-1,j-1]+1若i,j>

0且xi=yi

C[I,j]=max{C[i-1,j],C[i,j-1]}若i,j>

0且xi!

=yi

二维数组C，用C[i,j]记录Xi与Yj的LCS的长度如果我们是自底向上进行递推计算，那么在计算C[i,j]之前，C[i-1,j-1],C[i-1,j]与C[i,j-1]均已计算出来。

此时我们根据X[i]=Y[j]还是X[i]≠Y[j]，就可以计算出C[i,j]。

计算的理由：

求LCS（Xm-1，Y）的长度与LCS（X，Yn-1）的长度这两个问题不是相互独立的：

∵两者都要求LCS（Xm-1，Yn-1）的长度,因而具有重叠性。

另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。

20.用200～300字概述求最优二分搜索树算法的主要步骤。

算法中有哪几点最为关键？

记cij是最优子树Tij的耗费，则ci,k-1是最优子树Ti,k-1的耗费，ck,j是最优子树Tk,j的耗费。

考察以ak（i+1≤k≤j）为根、由结点bi，ai+1，bi+1，⋯，aj，bj构成的、耗费最小的树的总耗费：

该树的左子树必然是Ti,k-1，右子树必然是Tk,j。

这棵树的总耗费可分为三部分：

左子树、右子树和根。

由于Ti,k-1作为左子树接到结点ak之下时，其耗费增加wi,k-1，故左子树的耗费为：

ci,k-1+wi,k-1，同理，右子树的耗费为：

ck,j+wk,j，由于根ak的深度为0，按定义，根的耗费为pk。

因此，以ak为根、耗费最小的树的总耗费为：

ci,k-1+wi,k-1+ckj+wk,j+pk。

注意到，wi,k-1=qi+pi+1+qi+1+⋯+pk-1+qk-1，wk,j=qk+pk+1+qk+1+⋯+pj+qj，从而有wi,k-1+wkj+pk=qi+pi+1+qi+1+⋯+pk-1+qk-1+pk+qk+pk+1+qk+1+⋯+pj+qj=wij。

由此得到以ak为根、耗费最小的树的总耗费为：

ci,k-1+ckj+wi,j

由于pi（i=1,2,⋯,n）,qj（j=0,1,2,⋯,n）在初始时已经知道，若wi,j-1已知，则根据wi,j=wi,j-1+pj+qj可以计算出wij。

故当ci,k-1与ckj已知时，以ak为根的树的最小总耗费在O

（1）时间就可以计算出来。

分别计算以ai+1，ai+2，⋯，aj为根、含有结点bi，ai+1，bi+1，⋯，aj，bj的树的最小总耗费，从中选出耗费最小的树，此即最优子树Tij。

因此，最优子树Tij的耗费cij={cminjki≤<

jki≤<

i,k-1+ckj+wij}。

递推求cij及记录Tij的根的算法

本算法的关键点：

分析出最优二分搜索树具有最优子结构；

在计算中规模较小的最优子树在计算中要被多次用到。

Cij和Wij都是可以通过前面的计算递推得出的。

21.用200～300字概述二维流水作业调度算法的主要步骤。

求解该问题的算法如下。

1.建立长为2n的数组C，将a1,a2,┅,an依次放入C[1]~C[n]中，b1,b2,┅,bn依次放入C[n+1]~C[2n]中。

/*O（n）,下面将对这2n个数进行排序*/

2.对长为2n的数组D进行初始化：

D[1]~D[n]中依次放1,2,┅,n，D[n+1]~D[2n]中依次放-1,-2,┅,-n。

/*O（n）,分别对应于a1,a2,┅,an和b1,b2,┅,bn的下标*/

3.对数组C进行排序，D[k]始终保持与C[k]的对应关系。

（若C[i]与C[j]对换，则D[i]也与D[j]对换。

或将C，D放在同一结构体中。

）当a1,a2,┅,an及b1,b2,┅,bn按从小到大次序排好之后，

D[1]~D[2n]也就按从小到大的次序记录了这些ai和bj的下标即作业号（bj的下标前有一负号以区别于ai））。

/*O（nlogn）*/

4.将E[1]~E[n]全部置为"

No"

。

/*O（n），表示所有任务均尚未被安排*/

5.下标变量初始化：

i←1；

j←n；

k←1；

/*O

（1），i指向当前最左空位F[i]，放当前应最先安排的作业号;

*//*j指向当前最右空位F[j]，放当前应最后安排的作业号;

*//*k从1开始逐次增1，*//*D[k]（或-D[k]）按ai和bj从小到大的次序依次给出作业号*/

6.whilei≤j

do{/*作业尚未安排完毕，i从小到大,j从大到小*/

ifD[k]>

0then{ifE[D[k]]为"

then/*作业D[k]放在当前最左空位*/{F[i]←D[k];

i增1;

E[D[k]]置为"

Yes"

}}

elseifE[-D[k]]为"

then/*作业-D[k]放在当前最右空位*/{F[j]←-D[k];

j减1;

E[-D[k]]置为"

k增1；

}

22.什么是备忘录方法？

它在什么情况下使用较为有效？

备忘录方法是动态规划方法的变形。

与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。

若有大量的子问题无需求解时，用备忘录方法较省时。

但当无需计算的子问题只有少部分或全部都要计算时，

用递推方法比备忘录方法要好（如矩阵连乘，最优二分搜索树）。

23.简单不相交集的合并算法中为什么要引进集合的外部名和内部名？

：

若没有内部名，则每次合并时两个集合中的所有元素均要改名（改为K），这样，在n-1次Union中改名的时间就变为O（n2）。

24.什么是平摊分析？

平摊分析常用的手法有哪几种？

简单说明这几种手法的要点。

势能方法中引入平摊代价的意义是什么？

考虑n条指令执行的最坏时间复杂性。

即使某些指令执行时具有比较大的代价，

但利用平摊分析后对整体考虑，可以得到较小的平均代价。

平摊分析方法主要有：

聚集方法，会计方法和势能方法。

聚集方法：

全局考虑时间复杂性，把n条指令的耗费分为几类；

分别计算每一类耗费的总和，然后再把各类耗费总加起来。

会计方法：

利用几个操作之间的联系，在一个操作中预先支付下面某个操作的费用，以达到简化代价计算的目地。

势能方法：

设Ci为第i个操作的实际代价，D0为处理对象的数据结构的初始状态，

Di为第i个操作施加于数据结构Di-1之上后数据结构的状态，引入势函数Φ，Φ（Di）是与Di相关的势。

定义第i个操作的平摊代价为：

=Ci+（Φ（Di）-Φ（Di-1））（即实际代价加上势的变化），

25.为什么树结构下执行O（n）条带路径压缩的Union-Find指令只需要O（n*G（n））时间？

用平摊分析的聚集方法，把O（n）条Find指令的耗费分为三类：

1）O（n）条Find指令的根费用，

2）O（n）条Find指令的组费用，

3）O（n）条Find指令的路径费用。

根费用：

执行一条Find指令时，处理根及其儿子所需的费用。

一条Find指令只会碰到一个根（及其儿子），故O（n）条Find指令的根费用为O（n），这样，根及其儿子的费用已全部计算在内。

组费用：

若结点ik（0≤k≤m-2）与其父结点ik+1的秩不在同一个秩组中，则对ik收取一个组费用。

因最多有G（n）个组，故一条Find指令最多只会碰到G（n）个结点、其秩与其父结点的秩不在同一个秩组中，故O（n）条Find指令的组费用最多为O（n*G（n））。

路径费用：

由于其秩在组号为g的组中结点的个数不超过n/F（g），故组g中的结点的收取的路径费用不超过[n/F（g）]*[F（g）-（F（g-1）+1）]<

[n/F（g）]*F（g）=n。

因总共只有G（n）个组，故所有结点在O（n）条Find指令的执行中，收取的路径费用不超过O（n*G（n））。

三项费用总加起来，有O（n）+O（n*G（n））+O（n*G（n））=O（n*G（n））于是可得结论：

如果合并是是把小集合并入大集合，且执行Find指令时实施路径压缩，