文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 东南大学算法设计与分析复习题
侵权投诉

东南大学算法设计与分析复习题

东南大学算法设计与分析复习题 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,

上一页第2页

你可能喜欢

  • 程序设计基础复习题
  • 系统分析设计复习题
  • 平法复习题
  • 道路勘测设计复习题
  • 算法分析设计复习题
  • 算法设计分析复习题
  • 电路分析基础复习题

热门文档

相关文档

  • 东南大学算法设计与分析复习题

    东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...

  • 算法设计与分析复习题

    算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...

  • 算法设计与分析复习题

    算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...

  • 算法设计与分析复习题目及答案(物联班)

    算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...

  • 算法设计与分析考试复习题

    算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...

  • 算法分析与设计—部分复习题答案

    算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...

  • 计算机算法设计与分析复习题

    计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email