东南大学算法设计与分析复习题 2012年
答:在规模为n的数据元素集合中找出最大元和最小元, 至少需要3n/2-2次比较,即3n/2-2是找最大最小元算法的下界。当n=2k,或当n≠2k时,若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= (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于是有T(n)= Θ(n1.59),比Θ(n2)要好不少。
用200字概括Select(求第k小元)算法的主要思路。
答:1.若S<50,则采用堆排序的方法找出第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)。
当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,
东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...
算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...
算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...
算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...
算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...
算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...
算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...
算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...
计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....
热门文档