m*******r
发帖数: 98 | 1 k个array，每个长度为n，已排好序
给一个求median的算法，expected run time = O(k log^2(n))
已有rank(A1,A2,...Ak,x)能算x的rank，复杂度为O(k log(n)) | k*******d
发帖数: 1340 | 2 我对题目意思没理解清楚，求median是说k个array连起来的大array的median?
rank(A1,A2,...Ak,x)中的A1...Ak指的是什么？ | m*******r
发帖数: 98 | 3 对，求k个array连起来的median
A1,A2,..Ak就是这k个array
rank(A1,A2,..Ak,x)返回x在大array里的rank
【在 k*******d 的大作中提到】
: 我对题目意思没理解清楚，求median是说k个array连起来的大array的median?
: rank(A1,A2,...Ak,x)中的A1...Ak指的是什么？
| S*****H
发帖数: 90 | 4 Two nested binary searches. The outer one search for percentile (a number),
and the inner one search for rank.
【在 m*******r 的大作中提到】
: k个array，每个长度为n，已排好序
: 给一个求median的算法，expected run time = O(k log^2(n))
: 已有rank(A1,A2,...Ak,x)能算x的rank，复杂度为O(k log(n))
| m*******r
发帖数: 98 | 5 percentile就是rank吧
能具体说说吗？谢谢
number),
【在 S*****H 的大作中提到】
: Two nested binary searches. The outer one search for percentile (a number),
: and the inner one search for rank.
| S*****H
发帖数: 90 | 6 Outer search: binary search for F(x)=1/2. Starting with interval [a,b], try
x0=(a+b)/2.
The inner search is to calculate F(x0). For each array, inner search is
needed to count the frequency of <=x0. The sum of the frequency divided by
nk is F(x0).
【在 m*******r 的大作中提到】
: percentile就是rank吧
: 能具体说说吗？谢谢
:
: number),
|
|
