u*l
发帖数: 1943 | 1 问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。 |
r****o
发帖数: 1950 | 2 啥问题啊。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
|
u*l
发帖数: 1943 | 3 很简单，一串数，找前k个最小的。
【在 r****o 的大作中提到】
: 啥问题啊。
|
x****r
发帖数: 99 | |
w******1
发帖数: 520 | |
l*****a
发帖数: 14598 | 6 I am confused of the explaination
=============================================
Direct application of the quick sort based selection algorithm
The quick sort based selection algorithm can be used to find k smallest or
k largest elements. To find k smallest elements find the kth smallest
element using the median of medians quick sort based algorithm. After the
partition that finds the kth smallest element, all the elements smaller
than the kth smaller element will be present left to the kth eleme
【在 x****r 的大作中提到】
: 这个题可以O(n)做，见http://en.wikipedia.org/wiki/Selection_algorithm
|
y**i
发帖数: 1112 | 7 这个不是CLRS上的例题么
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
|
d**e
发帖数: 6098 | 8 它这里是说，如果用一个random的pivot，worse case可能是O(n^2)，
而用median of median找到一个好的pivot，需要O(n)，再应用Select找
k-th element，这里主要是花在partition上面，也是O(n)，worse case
也是O(n)，那么 (k-1) smallest/largest elements就在k-th的左/右边.
【在 l*****a 的大作中提到】
: I am confused of the explaination
: =============================================
: Direct application of the quick sort based selection algorithm
: The quick sort based selection algorithm can be used to find k smallest or
: k largest elements. To find k smallest elements find the kth smallest
: element using the median of medians quick sort based algorithm. After the
: partition that finds the kth smallest element, all the elements smaller
: than the kth smaller element will be present left to the kth eleme
|
k***e
发帖数: 556 | 9 linear selection
CLRS里面的
【在 u*l 的大作中提到】
: 很简单，一串数，找前k个最小的。
|
q*********u
发帖数: 280 | 10 你这个id太牛了。
鬼使神差这个，就恰好会在那种紧张的时候冒出来
问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。
【在 u*l 的大作中提到】
: 问了一个问题，
: 里面有用到排序的复杂度。
: 我知道是 nlogn, 居然鬼使神差的一直用logn.....
: 一紧张就出错阿。
|
