b***k
发帖数: 2673 | 1 说几个不同的计算机上各有一组长短不一的数组，
你无法把所有数组的数提出来排序，但你可以分别在各自的计算机里面排序，
给出一个算法得到所有这些数的中位数（median number）
这个是考programming的算法，似乎很经典啊，有什么好办法？ |
C*****d
发帖数: 69 | 2 Define a function f(x) which returns the number of elements smaller and
bigger than its input x in an array. On each machine f(x) can be easily
computed by sorting the array. At the global level, computing f(x) can be
easily done by adding up the returns from each machine.
Define another function p(x), which gives the percentage of elements in all
arrays that is smaller than x. obviously the p(x) function is monotonous. We
can use the bi-segment trick on p(x) to search for the x that gives us 50 |
c*********g
发帖数: 154 | 3 “Introduction of Algorithm”的“Medians and Order Statistics”有一个与之相
关的算法。
不过这道题M台计算机们各自为战，SELECT算法没法递归调用。假设数组的最大长度为N，那
么最坏情况下问题规模的递推公式大概是这样的：
T(nm)<=2T(n/2*m/2)+O(M)
其中O(M)在子问题中可以看做常数。由这个递推公式得到复杂度为O(sqrt(NM))。
但不要忘记，每个子问题都要做一遍O(M)，而子问题的个数有log_4(NM)个，所以这方
面的复杂度是log_4(NM)*O(M)。
两者综合考虑，最后的复杂度是O(sqrt(NM))。
还没有想到怎么做进一步的分析。感觉应该会有更好的算法使复杂度大概在O(NM*log(
NM))量级，即与排序算法一个量级。 |
t********a
发帖数: 810 | 4
以前听说过有asymtoptically比较强的算法, 用的是divide and conquer, 但没深究过
. LZ可以试着去google一下或问CS的教授.
【在 b***k 的大作中提到】
: 说几个不同的计算机上各有一组长短不一的数组，
: 你无法把所有数组的数提出来排序，但你可以分别在各自的计算机里面排序，
: 给出一个算法得到所有这些数的中位数（median number）
: 这个是考programming的算法，似乎很经典啊，有什么好办法？
|
c***z
发帖数: 6348 | 5 Is it possible that the real median falls outside of the initial bracket?
I think it is possible.
all
We
%.
【在 C*****d 的大作中提到】
: Define a function f(x) which returns the number of elements smaller and
: bigger than its input x in an array. On each machine f(x) can be easily
: computed by sorting the array. At the global level, computing f(x) can be
: easily done by adding up the returns from each machine.
: Define another function p(x), which gives the percentage of elements in all
: arrays that is smaller than x. obviously the p(x) function is monotonous. We
: can use the bi-segment trick on p(x) to search for the x that gives us 50
|
c***z
发帖数: 6348 | 6 If swapping is allowed, we can still use quickselect, but it is linear O(MN)
, where N is the largest length.
http://goanna.cs.rmit.edu.au/~stbird/Tutorials/QuickSelect.html
It can be improved to O(Mlog(N)) if the arrays are already sorted I think. |
c*********g
发帖数: 154 | 7 题目已经说了“你无法把所有数组的数提出来排序，但你可以分别在各自的计算机里面
排序”。所以quickselect没法用。
另外quickselect在最坏的情况下的复杂度是O(K^2)，其中K是欲排序的元素个数。虽然
这个“最坏”情况几乎不可能遇到。
那个“中位数的中位数”算法可以保证在最坏情况下也是O(K)，不过在这一题里不是太
适用。如果仅仅用那个idea的话，像我分析的，最坏情况下是O((MN)^2)
MN)
【在 c***z 的大作中提到】
: If swapping is allowed, we can still use quickselect, but it is linear O(MN)
: , where N is the largest length.
: http://goanna.cs.rmit.edu.au/~stbird/Tutorials/QuickSelect.html
: It can be improved to O(Mlog(N)) if the arrays are already sorted I think.
|
c***z
发帖数: 6348 | 8 It says we cannot sort, but doesn't say we cannot swap numbers between
different computers. So I am wondering...
Well, I know basically sorting is swapping, but still logically, swapping
might be allowed? |
b***k
发帖数: 2673 | 9 你们不要错误理解题意，原题（那个面试的人）其实也不在乎这个算法
是什么复杂度或者需要什么级别的计算量，他只需要你告诉他一个可行的算法就好了。
【在 c*********g 的大作中提到】
: 题目已经说了“你无法把所有数组的数提出来排序，但你可以分别在各自的计算机里面
: 排序”。所以quickselect没法用。
: 另外quickselect在最坏的情况下的复杂度是O(K^2)，其中K是欲排序的元素个数。虽然
: 这个“最坏”情况几乎不可能遇到。
: 那个“中位数的中位数”算法可以保证在最坏情况下也是O(K)，不过在这一题里不是太
: 适用。如果仅仅用那个idea的话，像我分析的，最坏情况下是O((MN)^2)
:
: MN)
|
c***z
发帖数: 6348 | 10 Oh yeah, then we do the naive O(n^2) double scan.
For each number, scan the list and score the number of numbers greater than
it. If it happen to be half of the total, stop. |
c***z
发帖数: 6348 | 11 I was thinking that maybe total sorting is not allowed because of not enough
space. And swapping uses just a little space...
But I realized that in that can we can do merge-sort in batches anyway... |
