b*********e
发帖数: 51 | 1 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
top k 的问题都用heap 呢？
按理说应该用最快的quick selection啊。 |
n*****x
发帖数: 686 | 2 我的理解是quick selection只能handle有限集合，heap可以搞stream
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
|
h*********n
发帖数: 11319 | 3 巧了，我今天就被问了这个，我先用了heap然后让我写quick select没写出来
真丢人
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
|
a********m
发帖数: 15480 | 4 硬写quick select?那不丢人吧。。。。
【在 h*********n 的大作中提到】
: 巧了，我今天就被问了这个，我先用了heap然后让我写quick select没写出来
: 真丢人
|
y*******a
发帖数: 138 | 5 理论上同是O(N),但用heap的结果似乎要快一点？没懂
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
|
L***s
发帖数: 1148 | 6 生背下来就好了…… 现场写容易搞错边界
【在 a********m 的大作中提到】
: 硬写quick select?那不丢人吧。。。。
|
L***s
发帖数: 1148 | 7 求 K-largest from N elements：
若用 MinHeap of size K，空间 O(K)，
时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
若用 QuickSelect，空间 O(N)，
时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
如果 N 非常大，或者是不确定长度的流，当然还是用 heap。 |
s****z
发帖数: 11 | 8 用median of median的quickselect就是O(N)，不用平均
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
|
W***o
发帖数: 6519 | 9 quickselect 是 in-place的，咋还算空间 O(N) ? 难道是算input的那个array 空间？
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
|
m**c
发帖数: 22 | |
