n*****j
发帖数: 66 | 1 【 以下文字转载自 EE 讨论区 】
发信人: nwpuxyj (赤壁), 信区: EE
标 题: 排序算法计算量问题！
发信站: BBS 未名空间站 (Thu Sep 15 05:31:25 2005)
有一个算法中用到一个排序：
有M个组，每个组有N个元素
现在需要从里面找到最大的M个
书上都给一个平均复杂度/计算量: O(MNlog(MN))
但我需要一个具体的数据来说明问题，比如需要多少次加减乘除操作？需要一个大致的数
目
望大虾们不吝赐教 |
d*******g
发帖数: 36 | 2
数
我自认不是大虾。
说说我的想法。
从你的问题描述来看，你的问题和“find top m elements from a sequence of n
elements"没有什么差别。你给出的复杂度（n log n) 就是排序的时间复杂度。
对于不同的alphabet,时间复杂度是不一样的。
你想得到的具体多少次..., 我想，你讲的是不是算法优化问题，更像编码优化问题。
以前我的北京工作，就专门搞编码优化。 我个人觉得，编码优化depends on 数据的
property.
【在 n*****j 的大作中提到】
: 【 以下文字转载自 EE 讨论区 】
: 发信人: nwpuxyj (赤壁), 信区: EE
: 标 题: 排序算法计算量问题！
: 发信站: BBS 未名空间站 (Thu Sep 15 05:31:25 2005)
: 有一个算法中用到一个排序：
: 有M个组，每个组有N个元素
: 现在需要从里面找到最大的M个
: 书上都给一个平均复杂度/计算量: O(MNlog(MN))
: 但我需要一个具体的数据来说明问题，比如需要多少次加减乘除操作？需要一个大致的数
: 目
|
n*****j
发帖数: 66 | 3 假设所有的N个数都是均匀分布的呢？
假设N=300, M=20，需要X次运算
或者N=100, M=20，需要Y次运算
我想知道X/Y是多少
【在 d*******g 的大作中提到】
:
: 数
: 我自认不是大虾。
: 说说我的想法。
: 从你的问题描述来看，你的问题和“find top m elements from a sequence of n
: elements"没有什么差别。你给出的复杂度（n log n) 就是排序的时间复杂度。
: 对于不同的alphabet,时间复杂度是不一样的。
: 你想得到的具体多少次..., 我想，你讲的是不是算法优化问题，更像编码优化问题。
: 以前我的北京工作，就专门搞编码优化。 我个人觉得，编码优化depends on 数据的
: property.
|
y***u
发帖数: 101 | 4
先找到第m大的,在扫描一遍: O(n)
【在 d*******g 的大作中提到】
:
: 数
: 我自认不是大虾。
: 说说我的想法。
: 从你的问题描述来看，你的问题和“find top m elements from a sequence of n
: elements"没有什么差别。你给出的复杂度（n log n) 就是排序的时间复杂度。
: 对于不同的alphabet,时间复杂度是不一样的。
: 你想得到的具体多少次..., 我想，你讲的是不是算法优化问题，更像编码优化问题。
: 以前我的北京工作，就专门搞编码优化。 我个人觉得，编码优化depends on 数据的
: property.
|
d*******g
发帖数: 36 | 5
Hi, man,
you can get Turning award if you are right :-)
Please do not worry, just for kidding.
And I know that you are not CS people.
【在 y***u 的大作中提到】
:
: 先找到第m大的,在扫描一遍: O(n)
|
s******n
发帖数: 240 | 6 be modest.
yixiu is watering everywhere, such as SODA, ESA, PODC, SIGMOD, etc
Check "Intro To Algo" section 9.3 selection in worst-case linear time
【在 d*******g 的大作中提到】
:
: Hi, man,
: you can get Turning award if you are right :-)
: Please do not worry, just for kidding.
: And I know that you are not CS people.
|
d*******g
发帖数: 36 | 7
Congratulations for so many high quality papers.
I know you are referring radix sorting.
But radix sorting cannot be used anywhere.
你怎么找到‘第m大的’if there are real numbers, even for integers?
【在 s******n 的大作中提到】
: be modest.
: yixiu is watering everywhere, such as SODA, ESA, PODC, SIGMOD, etc
: Check "Intro To Algo" section 9.3 selection in worst-case linear time
|
s******n
发帖数: 240 | 8
http://www.cs.fsu.edu/~cop4531/slideshow/chapter10/10-3.html
【在 d*******g 的大作中提到】
:
: Congratulations for so many high quality papers.
: I know you are referring radix sorting.
: But radix sorting cannot be used anywhere.
: 你怎么找到‘第m大的’if there are real numbers, even for integers?
|
d*******g
发帖数: 36 | 9
I am sorry that I make a serious mistake.
because from his problem, I jump to an open problem at once:
sorting X+Y.
Say sorry to yixiu also.
【在 s******n 的大作中提到】
:
: http://www.cs.fsu.edu/~cop4531/slideshow/chapter10/10-3.html
|
s*m
发帖数: 34 | 10 cft Yixiu
【在 d*******g 的大作中提到】
:
: I am sorry that I make a serious mistake.
: because from his problem, I jump to an open problem at once:
: sorting X+Y.
: Say sorry to yixiu also.
|
s******n
发帖数: 240 | 11 Never mind, It's quite understandable. :)
I like your discussion attitude.
//hug
【在 d*******g 的大作中提到】
:
: I am sorry that I make a serious mistake.
: because from his problem, I jump to an open problem at once:
: sorting X+Y.
: Say sorry to yixiu also.
|
A*********l
发帖数: 2005 | 12 Even without using the worst case linear selection algorithm, we can still get
a better solution compared the O(MN * log(MN)), right? I think we can get O(
MN * logM). If M is small, this algorithm is very close to linear time. Even
if M is large, it would still be much better than O(MN * log(MN)).
Use a priority queue of size M. Since the M largest numbers are wanted, this
queue is a min-queue. Insert each element into this queue, and after it is
done, what's left in the queue should be the M l
【在 s******n 的大作中提到】
: Never mind, It's quite understandable. :)
: I like your discussion attitude.
: //hug
|
