找median有O(N)的算法吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

找median有O(N)的算法吗？

找median有O(N)的算法吗？# JobHunting - 待字闺中

l*z2012-05-23 07:05

1 楼

unsorted int array.
max and min 都是easy O(N). Median 有吗？

O*i2012-05-23 07:05

2 楼

CLRS?

【在 l*****z 的大作中提到】

: unsorted int array.
: max and min 都是easy O(N). Median 有吗？

l*z2012-05-23 07:05

3 楼

具体说说。。

O*i2012-05-23 07:05

4 楼

有章讲了那个median of median的quick select
不过O(n)的常系数可能会很大

【在 l*****z 的大作中提到】

: 具体说说。。

d*x2012-05-23 07:05

5 楼

一般只要用randomized partition就行了

【在 O******i 的大作中提到】

: 有章讲了那个median of median的quick select
: 不过O(n)的常系数可能会很大

d*e2012-05-23 07:05

6 楼

方法和quicksort差不多。
在quicksort里，选择一个pivot value，完成partition，这时候有大于pivot value和
小于pivot value的两个序列，都需要递归的用quick sort排序。
如果要求第k大的数，只要判断一下该数在哪个序列里，然后对那一个序列再找第k'个
数就可以了。
该方法平均时间成本是O(n)，如果选pivot时增加一些限制，可以保证最坏时间成本是O
(n)。

【在 l*****z 的大作中提到】

: 具体说说。。

f*n2012-05-23 07:05

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*z2012-05-23 07:05

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*e2012-05-23 07:05

9 楼

不大吧，median of median大概引入10/3这么个常数倍。

【在 O******i 的大作中提到】

: 有章讲了那个median of median的quick select
: 不过O(n)的常系数可能会很大

d*x2012-05-23 07:05

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*n2012-05-23 07:05

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*n2012-05-23 07:05

12 楼

用selection algorithm排完序再取median应该满足要求吧...

a*m2012-05-23 07:05

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