l*****z
发帖数: 3022 | 1 unsorted int array.
max and min 都是easy O(N). Median 有吗？ |
O******i
发帖数: 269 | 2 CLRS?
【在 l*****z 的大作中提到】
: unsorted int array.
: max and min 都是easy O(N). Median 有吗？
|
l*****z
发帖数: 3022 | |
O******i
发帖数: 269 | 4 有章讲了那个median of median的quick select
不过O(n)的常系数可能会很大
【在 l*****z 的大作中提到】
: 具体说说。。
|
d**********x
发帖数: 4083 | 5 一般只要用randomized partition就行了
【在 O******i 的大作中提到】
: 有章讲了那个median of median的quick select
: 不过O(n)的常系数可能会很大
|
d*******e
发帖数: 24 | 6 方法和quicksort差不多。
在quicksort里，选择一个pivot value，完成partition，这时候有大于pivot value和
小于pivot value的两个序列，都需要递归的用quick sort排序。
如果要求第k大的数，只要判断一下该数在哪个序列里，然后对那一个序列再找第k'个
数就可以了。
该方法平均时间成本是O(n)，如果选pivot时增加一些限制，可以保证最坏时间成本是O
(n)。
【在 l*****z 的大作中提到】
: 具体说说。。
|
f*******n
发帖数: 12623 | 7 This is not good. It has worst-case O(n^2)
What they were asking for is WORST-CASE O(n).
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general
是O
【在 d*******e 的大作中提到】
: 方法和quicksort差不多。
: 在quicksort里，选择一个pivot value，完成partition，这时候有大于pivot value和
: 小于pivot value的两个序列，都需要递归的用quick sort排序。
: 如果要求第k大的数，只要判断一下该数在哪个序列里，然后对那一个序列再找第k'个
: 数就可以了。
: 该方法平均时间成本是O(n)，如果选pivot时增加一些限制，可以保证最坏时间成本是O
: (n)。
|
l*****z
发帖数: 3022 | 8 这个答案好。看来还真不是那么简单的。
【在 f*******n 的大作中提到】
: This is not good. It has worst-case O(n^2)
: What they were asking for is WORST-CASE O(n).
: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general
:
: 是O
|
j********e
发帖数: 1192 | 9 不大吧，median of median大概引入10/3这么个常数倍。
【在 O******i 的大作中提到】
: 有章讲了那个median of median的quick select
: 不过O(n)的常系数可能会很大
|
d**********x
发帖数: 4083 | 10 but this is practically good.
The worst case O(N) method has a very large hidden constant factor which
makes it not practical at all.
value和
'个
【在 f*******n 的大作中提到】
: This is not good. It has worst-case O(n^2)
: What they were asking for is WORST-CASE O(n).
: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general
:
: 是O
|
|
|
R********n
发帖数: 519 | 11 恩，感觉讨论complexity，worst case or average，确实要分开说
【在 d**********x 的大作中提到】
: but this is practically good.
: The worst case O(N) method has a very large hidden constant factor which
: makes it not practical at all.
:
: value和
: '个
|
a***n
发帖数: 16 | 12 用selection algorithm排完序再取median应该满足要求吧... |
a********m
发帖数: 15480 | 13 这俩是一回事吧。
【在 f*******n 的大作中提到】
: This is not good. It has worst-case O(n^2)
: What they were asking for is WORST-CASE O(n).
: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general
:
: 是O
|
y***u
发帖数: 174 | 14 quick sort, 一半，一半，一半。。O(n)+O(n/2)+O(n/4)+..
【在 l*****z 的大作中提到】
: unsorted int array.
: max and min 都是easy O(N). Median 有吗？
|
f*******n
发帖数: 12623 | 15 不一定是一半
【在 y***u 的大作中提到】
: quick sort, 一半，一半，一半。。O(n)+O(n/2)+O(n/4)+..
|
