寄托天下
查看: 1769|回复: 6
打印 上一主题 下一主题

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

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

使用道具 举报

Rank: 4

声望
0
寄托币
1521
注册时间
2005-1-12
精华
1
帖子
4
沙发
发表于 2005-10-31 11:01:42 |只看该作者
看不懂这到题
GRE作文互动论坛 -> GRE考试综合论坛 -> TOEFL考试讨论专版  -> GRE_SUB -> 美国留学 -> VISA 美国签证 -> 行前准备::飞跃同期声 -> 异乡岁月※海外申请

使用道具 举报

Rank: 2

声望
0
寄托币
93
注册时间
2005-8-3
精华
0
帖子
0
板凳
发表于 2005-10-31 18:04:32 |只看该作者
看不懂这个题,估计考的是merge的复杂度和链表查找的复杂度吧

使用道具 举报

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 你认为呢? 讨论一下。

使用道具 举报

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).

使用道具 举报

Rank: 2

声望
0
寄托币
116
注册时间
2005-5-28
精华
0
帖子
0
6
发表于 2005-11-3 16:46:54 |只看该作者
因为题目中说插入的时候先放在临时队列里O(1),到查找的时候才进行merge,所以merge完了以后是有序的,再和n归并 O(m+n)

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

使用道具 举报

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)

使用道具 举报

RE: 计算机指南上的几道题问一下. [修改]

问答
Offer
投票
面经
最新
精华
转发
转发该帖子
计算机指南上的几道题问一下.
https://bbs.gter.net/thread-356737-1-1.html
复制链接
发送
回顶部