《东南大学算法设计与分析复习题18页》由会员分享，可在线阅读，更多相关《东南大学算法设计与分析复习题18页（18页珍藏版）》请在金锄头文库上搜索。
1、什么是最坏情况时间复杂性？什么是平均情况时间复杂性？答：最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。 平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 （一般均假设每种输入情况以等概率出现）。什么是相互独立的函数序列？何时称函数项k(x)能被其它函数项线性表出？答：设0(x), 1(x), 2(x), . ,n(x), .是某一数域上的函数序列， （x的值以及k(x)（k=0,1,2, ）的值都在同一个数域中） 任取k(x)（k=0,1,2, ），不存在数域中的数1，2，p，使得k (x) = 1i1(x) + 2i2 (x) + + pip (
2、x) ，即任何一个函数项k(x)不能被其它函数项线性表出。根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？答：1.若方程(*)恰有r个互不相同的特征根1，2，r (即ij时有ij)，则齐次方程(*)的解为 anA1+ A2+ +Ar(齐通解，即齐次方程的通解) （A1Ar为待定系数，可由r个连续的边界条件唯一确定） 2若1，2是(*)方程的一对共扼复数根和， eiei.则这两个根对应的解的部分为Ancos(n)+Bnsin(n) (A,B为实的待定系数)3若是(*)方程的k重根，则对应的解的部分为 C1n+ C2 nn+ C3 n2n+ +Ck nk-1n (C1Ck为待定常数)4
3、若(*)方程中的f(n)0(非齐次)，且q(n)是(*)的一个解， 则(*)方程的解为： (*)的齐通解（含有待定系数）+ q(n) （非齐特解）， （齐通解中的待定系数由边界条件唯一确定）求和中的通项与积分中的被积函数之间有什么样的关系？答：求和中的通项的表达形式一般就是被积函数，一般用放缩的方法求得通项得上下界。分治法求最大、最小元算法的主要思想？答：当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。 当n2时，可以把n个数据元素分为大致相等的两半， 一半有n/2个数据元素，而另一半有n/2个数据元素。 先分别找出各自组中的最大元和最小元，然后 将两个最大元进行比较，就可得n个元
4、素的最大元； 将两个最小元进行比较，就可得n个元素的最小元。求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？答：在规模为n的数据元素集合中找出最大元和最小元， 至少需要3n/2-2次比较，即3n/2-2是找最大最小元算法的下界。当n=2k,或当n2k时，若n是若干2的整数幂之和，（e.g. 42=32+8+2）， 则算法的时间复杂度仍可达到3n/2-2。如何用分治法求两个n位二进制数x和y的乘积？算法的时间复杂度是多少？答：若n=2k，则x可表为a2n/2+b，y可表为c2n/2+d (如图), 其中a, b, c, d均为n/2位二进制数。 于是x*y
5、= (a2n/2+b) (c2n/2+d) = ac2n + (ad+bc)2n/2 + bd，计算式ac2n + (ad+bc)2n/2 + bd中的ad+bc可写为： 而(ad+bc)= (a+b) (d+c) - ac - bd, 因此在ac和bd计算出之后， 只要再做4次加减法，一次（n/2位数的）乘法就可以计算出ad+bc。 而原来计算(ad+bc)需要做2次乘法、一次加法； 新的计算公式比原方法少做了一次乘法。T(n)=3T(n/2) + (n)，即a=3, b=2, f(n)=(n)。 此时有：= = naLogbn32Logn1.59，并仍有f(n)=O()， )(aLogbn
6、于是有T(n)= (n1.59)，比(n2)要好不少。用200字概括Select（求第k小元）算法的主要思路。答：1.若S50，则采用堆排序的方法找出第k小的元素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)。 当sim时将si放入数组S3； 在得到的3个集合中，S1中的数均小于m； S2中的数均等于m；S3中的数均大于m。 6. 按照k值大小，共可分
7、成下列三种情况（注意S2至少有一个元素m）： k|S1|；|S1|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|S1|+|S2|，则第k小元素必定大于m，因此在S3中。 而且此时该元素在S3中应为第k-|S1|-|S2|小的元素。 于是递归调用
8、Select（k-|S1|-|S2|, S3）， 就可以获得S中的第k小元素。 因小于等于m的数据元素至少有3n/10-6个1的情况下，T(n)分别为什么？1及p+q时间复杂度为T(n)=T(p*n)+T(q*n)+a*n时，在p+q答：T(n)a*n*k=0(p+q)k矩阵相乘算法目前最好的时间复杂度是多少？答：目前矩阵乘法最好的时间复杂度是能做到O（n2.376）叙述Strassen矩阵相乘算法的主要思路和意义。答：把矩阵A，B分成4个规模为n/2的子矩阵快C11=A11B11+A12B21, C12=A11B12+A12C21=A21B11+A22B21, C22=A21B12+A22B
9、22同时引入下列Mi(i=1,2.7) 则计算两个n阶矩阵的乘法为7对n/2阶矩阵的乘法(时间为7T(n/2),以及18对n/2阶矩阵的加减法则递归方程为T(n)=7T(n/2)+ (n2),由主定理得T(n)= (n2.81). Strassen矩阵相乘算法意义在于打破了人们认为矩阵乘法得时间复杂度为（n3）得固定看法。什么是最长公共子序列问题？在求LCS的算法中，Ci,j是如何计算的？为什么需要这样计算？答：若ZX，Z0且xi=yiCI,j=maxCi-1,j,Ci,j-1 若i,j0且xi!=yi二维数组C，用Ci,j记录Xi与Yj的LCS的长度 如果我们是自底向上进行递推计算，那么在计
10、算Ci,j之前， Ci-1,j-1, Ci-1,j与Ci,j-1均已计算出来。此时我们 根据Xi=Yj还是XiYj，就可以计算出Ci,j。 计算的理由：求LCS(Xm-1，Y)的长度与LCS(X，Yn-1)的长度 这两个问题不是相互独立的： 两者都要求LCS(Xm-1，Yn-1)的长度, 因而具有重叠性。 另外两个序列的LCS中包含了两个序列的前缀的LCS， 故问题具有最优子结构性质 考虑用动态规划法。用200300字概述求最优二分搜索树算法的主要步骤。算法中有哪几点最为关键？答：记cij是最优子树Tij的耗费， 则ci,k-1是最优子树Ti,k-1的耗费，ck,j是最优子树Tk,j的耗费。
11、考察以ak (i+1kj)为根、由结点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
12、,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，
13、aj，bj的树的最小总耗费， 从中选出耗费最小的树，此即最优子树Tij。 因此，最优子树Tij的耗费cij=cminj k i j k i i,k-1+ckj+wij。 递推求cij及记录Tij的根的算法本算法的关键点：分析出最优二分搜索树具有最优子结构；在计算中规模较小的最优子树在计算中要被多次用到。Cij和Wij都是可以通过前面的计算递推得出的。有了Tij的根的序号后，如何构造出最优二分搜索树？答：设Tij的根为ak (rij记录到的值是k)，则从根开始建结点。 Build-tree(i,j,r,A) /*建立最优子树Tij*/ If ij return nill; pointernewn
14、ode(nodetype); krij; /*必有i m j*/ pointervalueAk; /*Ak即ak*/ pointerleftsonBuildtree(i,k-1,r,A); /*建立最优左子树Ti,k-1*/ pointerrightsonBuildertree(k,j,r,A); /*建立最优右子树Tk,j*/ return pointer; Francis Yao的办法为什么会把算法时间复杂度从O(n3)降到O(n2)？答：Th: 如果最小耗费树Ti,j-1和Ti+1,j的根分别为ap和aq，则必有 pq 最小耗费树Tij的根ak满足pkq。 （证明略。）有了上述定理，我们无需在ai+1aj之间去一一尝试，使得找到的ak为根时，ci,k-1+ckj+wij为最小，而只要从apaq之间去找一个根即可。算法时间复杂度为(n2)的证明： 首先注意Ti,j-1和Ti+1,j的规模恰好比Ti,j小1。由于算法是按树中结点的个数（即规模）从小到大计算的，故在计算rij
