算法设计与分析算法考试2012年答案

VIP免费

2025-01-13 3 0 31KB 1 页 5.9玖币

侵权投诉

一、判断题

1.F

2.F

3.T

4.F

5.F

6.F

7.F

8.F

9.T

10.F

11.F

12.T

13.F

14.T

二、问答题

同2011 年，略

三、蛮力算法：对每一个数需要判断它是否是多数元素，两重循环，时间复杂度为

O(n^2)。

变治算法：

多数元素一定是众数，所以求出众数判断众数的出现次数是否多于。

先对数组进行排序，找出连续长度大于的数。

伪代码：

FindTheMostNumber(A,n)

for i = 1 to n do

length=0

val = A[i]

while i+length<=n and A[i+length]==val do

Length++

if length > n/2

Then return A[i]

i = i + length

时间复杂度：排序需要，查找需要，因此总的复杂度为。

Ps:还有 O(n)的算法（Hash 方法，还有一种只遍历一次的做法）。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

已全部加载

摘要：

一、判断题1.F2.F3.T4.F5.F6.F7.F8.F9.T10.F11.F12.T13.F14.T二、问答题同2011年，略三、蛮力算法：对每一个数需要判断它是否是多数元素，两重循环，时间复杂度为O(n^2)。变治算法：多数元素一定是众数，所以求出众数判断众数的出现次数是否多于。先对数组进行排序，找出连续长度大于的数。伪代码：FindTheMostNumber(A,n)fori=1tondolength=0val=A[i]whilei+lengthn/2ThenreturnA[i]i=i+length时间复杂度：排序需要，查找需要，因此总的复杂度为。Ps:还有O(n)的算法（Hash方法...

展开>> 收起<<

算法设计与分析算法考试2012年答案.doc

共1页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析算法考试2012年答案

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: