N***m
发帖数: 4460 | |
g**e
发帖数: 6127 | 2 use min heap
【在 N***m 的大作中提到】
|
N***m
发帖数: 4460 | 3 Thanks.
【在 g**e 的大作中提到】
: use min heap
|
D*******a
发帖数: 3688 | 4 even naive implementation is O(N) because 5 is constant |
g*********s
发帖数: 1782 | 5 sorry, why min heap instead of max heap?
【在 g**e 的大作中提到】
: use min heap
|
z****e
发帖数: 2024 | 6 1.modify数组,但无需额外内存,nth_element can do the work.
2.数组不变,额外常数内存,用heap.
3.数组不变,额外最小内存,暴利扫描5次,仍然O(N). |
P********e
发帖数: 2610 | 7 heap其实开销不小
这种简单问题,不需要heap
【在 g**e 的大作中提到】
: use min heap
|
S**I
发帖数: 15689 | 8 partial_sort is better than nth_element in this case
【在 z****e 的大作中提到】
: 1.modify数组,但无需额外内存,nth_element can do the work.
: 2.数组不变,额外常数内存,用heap.
: 3.数组不变,额外最小内存,暴利扫描5次,仍然O(N).
|
g*********s
发帖数: 1782 | 9 not necessarily true.
heap can be implemented by array. so no extra memory cost needed.
【在 P********e 的大作中提到】
: heap其实开销不小
: 这种简单问题,不需要heap
|
g*********s
发帖数: 1782 | 10 yes, partial_sort is heap sort.
【在 S**I 的大作中提到】
: partial_sort is better than nth_element in this case
|
|
|
t****t
发帖数: 6806 | 11 那你不如说说这个问题里heap有些什么开销?
【在 P********e 的大作中提到】
: heap其实开销不小
: 这种简单问题,不需要heap
|
N***m
发帖数: 4460 | 12 re. It is always good to hear about details
【在 t****t 的大作中提到】
: 那你不如说说这个问题里heap有些什么开销?
|
z****e
发帖数: 2024 | 13 如果不是要求5个最大的也排序的话,无需partial_sort.
【在 S**I 的大作中提到】
: partial_sort is better than nth_element in this case
|
P********e
发帖数: 2610 | 14 就5个数字，搞一个heap不觉得开销大吗？
insert/delete in heap are 0(logn)
【在 t****t 的大作中提到】
: 那你不如说说这个问题里heap有些什么开销?
|
g*****g
发帖数: 34805 | 15 反了吧，5个数字，还有啥开销大的？
就5个数字，手写排序我肯定用冒泡，
谁说冒泡不行我跟谁急。
【在 P********e 的大作中提到】
: 就5个数字，搞一个heap不觉得开销大吗？
: insert/delete in heap are 0(logn)
|
b********e
发帖数: 58 | 16 Perhaps one scanning is enough.
1) Just locate an array of 5, initialize it with lower limit;
2) For every number read in, compare with these 5 slots;
3) insert/replace the right slot as it goes.
So N read, maximum 5N comparisons.
Do I miss anything here? |
t****t
发帖数: 6806 | 17 just tell me the total complexity of doing it with a heap.
【在 P********e 的大作中提到】
: 就5个数字，搞一个heap不觉得开销大吗？
: insert/delete in heap are 0(logn)
|
D*******a
发帖数: 3688 | 18 this n is not that N
【在 P********e 的大作中提到】
: 就5个数字，搞一个heap不觉得开销大吗？
: insert/delete in heap are 0(logn)
|
t****t
发帖数: 6806 | 19 oh i got it, you thought we build a heap of 5 and repeatly insert into it?
that's really a novel way of doing it...
【在 P********e 的大作中提到】
: 就5个数字，搞一个heap不觉得开销大吗？
: insert/delete in heap are 0(logn)
|
P********e
发帖数: 2610 | 20 用max heap就是O(kn+heap的开销)
【在 t****t 的大作中提到】
: just tell me the total complexity of doing it with a heap.
|
|
|
k***s
发帖数: 277 | 21 if use partition sort and merge, should be O(n+5lg(n)) in time
【在 P********e 的大作中提到】
: 用max heap就是O(kn+heap的开销)
|
t****t
发帖数: 6806 | 22 显然不对
【在 P********e 的大作中提到】
: 用max heap就是O(kn+heap的开销)
|
P********e
发帖数: 2610 | 23 如果你用max heap的话，没有extra memory。
【在 t****t 的大作中提到】
: 显然不对
|
t****t
发帖数: 6806 | 24 don't distract from the subject. just tell us what's the complexity of using
a heap to solve the problem, and what's the "extra cost" you mentioned.
【在 P********e 的大作中提到】
: 如果你用max heap的话，没有extra memory。
|
P********e
发帖数: 2610 | 25 晕倒
我不是说了 O(kn + heap的开销）
我指维护heap的开销，比如你heap里有1，2，3，4，5你要插入6的开销。
using
【在 t****t 的大作中提到】
: don't distract from the subject. just tell us what's the complexity of using
: a heap to solve the problem, and what's the "extra cost" you mentioned.
|
t****t
发帖数: 6806 | 26 below was one of my previous post. to make it clear, i was being sarcastic
by saying you have a novel algorithm; you don't have a novel algorithm, you
have a wrong algorithm. when we said we want to use heap to find 5 max
number, we meant to use a heap of N, not heap of 5.
发信人: thrust (祝阳阳早日康复), 信区: Programming
标 题: Re: N个数字里面找出最大的5个数字的复杂度是什么？O(N)?
发信站: BBS 未名空间站 (Mon Jan 24 20:22:51 2011, 美东)
oh i got it, you thought we build a heap of 5 and repeatly insert into it?
that's really a novel way of doing it...
【在 P********e 的大作中提到】
: 晕倒
: 我不是说了 O(kn + heap的开销）
: 我指维护heap的开销，比如你heap里有1，2，3，4，5你要插入6的开销。
:
: using
|
p***o
发帖数: 1252 | 27 What's the point to use a heap of N to find 5 max number
I don't get it ... Isn't it as simple as scanning the sequence
once while keeping 5 max number so far?
you
【在 t****t 的大作中提到】
: below was one of my previous post. to make it clear, i was being sarcastic
: by saying you have a novel algorithm; you don't have a novel algorithm, you
: have a wrong algorithm. when we said we want to use heap to find 5 max
: number, we meant to use a heap of N, not heap of 5.
: 发信人: thrust (祝阳阳早日康复), 信区: Programming
: 标 题: Re: N个数字里面找出最大的5个数字的复杂度是什么？O(N)?
: 发信站: BBS 未名空间站 (Mon Jan 24 20:22:51 2011, 美东)
: oh i got it, you thought we build a heap of 5 and repeatly insert into it?
: that's really a novel way of doing it...
|
t****t
发帖数: 6806 | 28 i didn't say it's the best way (obviously it depends on N). someone else
suggested it. but it's not a bad way either. in fact, building a heap of N
is O(N) and adjusting after 1st number is O(logN) for each number. if you
count the real comparison times, its about 3N+klogN, still not bad.
on the other hand, "keeping 5 max number" is not trivial either. consider
heap algorithm is standard, i don't see point of not using it.
【在 p***o 的大作中提到】
: What's the point to use a heap of N to find 5 max number
: I don't get it ... Isn't it as simple as scanning the sequence
: once while keeping 5 max number so far?
:
: you
|
P********e
发帖数: 2610 | 29 晕倒，你要这样，我也sarcasm
1。 it is repeatedly, not repeatly.
2。 insert is a transitive verb.
you have to say insert something into it.
you
【在 t****t 的大作中提到】
: below was one of my previous post. to make it clear, i was being sarcastic
: by saying you have a novel algorithm; you don't have a novel algorithm, you
: have a wrong algorithm. when we said we want to use heap to find 5 max
: number, we meant to use a heap of N, not heap of 5.
: 发信人: thrust (祝阳阳早日康复), 信区: Programming
: 标 题: Re: N个数字里面找出最大的5个数字的复杂度是什么？O(N)?
: 发信站: BBS 未名空间站 (Mon Jan 24 20:22:51 2011, 美东)
: oh i got it, you thought we build a heap of 5 and repeatly insert into it?
: that's really a novel way of doing it...
|
P********e
发帖数: 2610 | 30 我的point是
O(kn)就不是true O(n),有的好方法为什么不用呢。
keep 5 max number is easy though not trivial:
try binary search tree and implement it as an array.
【在 t****t 的大作中提到】
: i didn't say it's the best way (obviously it depends on N). someone else
: suggested it. but it's not a bad way either. in fact, building a heap of N
: is O(N) and adjusting after 1st number is O(logN) for each number. if you
: count the real comparison times, its about 3N+klogN, still not bad.
: on the other hand, "keeping 5 max number" is not trivial either. consider
: heap algorithm is standard, i don't see point of not using it.
|
|
|
g**e
发帖数: 6127 | 31 用 min heap of 5可以吧，保存最大的5个数。root是最大5个数里最小的。每次都跟
root比，如果比root大就替换root，并sift down。
这样一遍扫描下来min heap里面就是最大的5个数了
当然跟最直观的扫描一遍保存5个最大的数没太大分别，比较次数少一点
you
【在 t****t 的大作中提到】
: below was one of my previous post. to make it clear, i was being sarcastic
: by saying you have a novel algorithm; you don't have a novel algorithm, you
: have a wrong algorithm. when we said we want to use heap to find 5 max
: number, we meant to use a heap of N, not heap of 5.
: 发信人: thrust (祝阳阳早日康复), 信区: Programming
: 标 题: Re: N个数字里面找出最大的5个数字的复杂度是什么？O(N)?
: 发信站: BBS 未名空间站 (Mon Jan 24 20:22:51 2011, 美东)
: oh i got it, you thought we build a heap of 5 and repeatly insert into it?
: that's really a novel way of doing it...
|
y***d
发帖数: 2330 | 32 可以找 N 个相同的弹簧，挂在一个水平的杆上，每个上面放上重量等同于相应数字的
电子设备，然后降低杆的高度，电子设备触地时就会通过扬声器报出自己相应的数字；
这样只要记录前 5 个报数的电子设备就可以了。
【在 g**e 的大作中提到】
: 用 min heap of 5可以吧，保存最大的5个数。root是最大5个数里最小的。每次都跟
: root比，如果比root大就替换root，并sift down。
: 这样一遍扫描下来min heap里面就是最大的5个数了
: 当然跟最直观的扫描一遍保存5个最大的数没太大分别，比较次数少一点
:
: you
|
N***m
发帖数: 4460 | 33 你这是并行处理阿
【在 y***d 的大作中提到】
: 可以找 N 个相同的弹簧，挂在一个水平的杆上，每个上面放上重量等同于相应数字的
: 电子设备，然后降低杆的高度，电子设备触地时就会通过扬声器报出自己相应的数字；
: 这样只要记录前 5 个报数的电子设备就可以了。
|
p***o
发帖数: 1252 | 34 需要同步，估计快不起来。
【在 N***m 的大作中提到】
: 你这是并行处理阿
|
s*****g
发帖数: 5159 | 35 quick select, \Theta(N).
【在 N***m 的大作中提到】
|
