寄托家园留学论坛 › 论坛 › 寄托学术类备考版 › GRE考试综合版 › GRE_SUB › 计算机指南上的几道题问一下.

返回列表

查看: 1769|回复: 6

计算机指南上的几道题问一下. [复制链接]

yuren78
UID: 2111432

寄托新兵

Rank: 2

声望: 0
寄托币: 73
注册时间: 2005-6-26
精华: 0
帖子: 0

电梯直达

楼主

发表于 2005-10-31 09:59:27 |只看该作者 |倒序浏览

P 188 - 19, 20

有序链表的插入操作采用: 把插入的放在一个临时队列里, 查找是用MERGE, 再和原来的队列归并. 有N个元素, 插入m 个元素, 最后找一次, 问 1 >MERGE 操作的时间复杂度; 2> 插入的复杂度.

0 0

使用道具举报

Autosea
UID: 192045

中级会员

Rank: 4

声望: 0
寄托币: 1521
注册时间: 2005-1-12
精华: 1
帖子: 4

沙发

发表于 2005-10-31 11:01:42 |只看该作者

看不懂这到题

GRE作文互动论坛 -> GRE考试综合论坛 -> TOEFL考试讨论专版 -> GRE_SUB -> 美国留学 -> VISA 美国签证 -> 行前准备::飞跃同期声 -> 异乡岁月※海外申请

双非DIY美硕申请总结

使用道具举报

youarestupid
UID: 2123815

寄托新兵

Rank: 2

声望: 0
寄托币: 93
注册时间: 2005-8-3
精华: 0
帖子: 0

板凳

发表于 2005-10-31 18:04:32 |只看该作者

看不懂这个题，估计考的是merge的复杂度和链表查找的复杂度吧

使用道具举报

maverick2005
UID: 2104907

寄托新兵

Rank: 2

声望: 0
寄托币: 116
注册时间: 2005-5-28
精华: 0
帖子: 0

地板

发表于 2005-11-2 23:52:12 |只看该作者

感觉这个题书中答案有问题
1.
MERGE m元素操作的时间复杂度是O(mlogm) 然后和原有n的有序列表归并O(m+n)
2.
插入不用排序应该是O(1)

这是我的想法，yuren78 你认为呢？讨论一下。

使用道具举报

yuren78
UID: 2111432

寄托新兵

Rank: 2

声望: 0
寄托币: 73
注册时间: 2005-6-26
精华: 0
帖子: 0

5楼

发表于 2005-11-3 08:10:42 |只看该作者

我也不是很懂这个题.

我同意 MERGE m元素操作的时间复杂度是O(mlogm) ,

But what do you mean "原有n的有序列表归并O(m+n)", 插入不用排序应该是O(1).

使用道具举报

maverick2005
UID: 2104907

寄托新兵

Rank: 2

声望: 0
寄托币: 116
注册时间: 2005-5-28
精华: 0
帖子: 0

6楼

发表于 2005-11-3 16:46:54 |只看该作者

因为题目中说插入的时候先放在临时队列里O(1)，到查找的时候才进行merge，所以merge完了以后是有序的，再和n归并 O(m+n)

主要是题目说的不清楚，想的不一样，答案自然不一样。

使用道具举报

litsquirrel
UID: 2151090

新手上路

Rank: 1

声望: 0
寄托币: 27
注册时间: 2005-10-24
精华: 0
帖子: 0

7楼

发表于 2005-11-4 19:03:02 |只看该作者

愚见

本题中的插入操作的含义是：将1个元素与 n+x (x=0~m-1)个元素构成的两个队列merge。(不过题目内容有些含糊，让人费解。)
由于使用链表，只需要计算查找的复杂度：O(n+x) ，插入时为：O(1)。
m个元素插入的复杂度分别为：O(n),O(n+1),...O(n+m-1)
其和<= O((m+n)m)

使用道具举报