c++ - 计算排序数组的成对绝对和的中位数的高效算法

Question

我正在尝试想出一个快速算法来计算 数量 b[i]= med |y_i+y_j|, 1<=j!=i<=n什么时候 y_1,...,y_n已经排序(所以 b[] 是一个 vector 与 y[] 长度相同). 我将假设 y[] 的所有元素是独一无二的 并且 n 是偶数。

因此，下面的代码计算了 b[i]是天真的(O(n**2))方式: (为了方便，我用 R 写了这个，但我是语言不可知论者)

n<-30
a_fast<-b_slow<-rep(NA,n)
y<-sort(rnorm(n,100,1))
z<-y
for(i in 1:n){
    b_slow[i]<-median(abs(y[-i]+y[i]))
}   

我在 O(n) 中有一个初步的建议——如下—— . 但只有在 y[] 时才有效包含正数。

我的问题是:我应该如何改变快速算法 在y[]时也能工作包含正面和 负数？这可能吗？

编辑:

和下面的代码(暂定)O(n)方法 (为了方便，我用 R 写了这个，但我是语言不可知论者)

tryA<-floor(1+(n-1)/2+1)
tryB<-floor(1+(n-1)/2)
medA<-y[tryA]
medB<-y[tryB]
for(i in 1:(tryA-1)){
        a_fast[i]<-medA+y[i]
}
for(i in tryA:n){
        a_fast[i]<-medB+y[i]
}

简单示例:

简单的说明性示例。如果我们有一个长度为 4 的 vector

-3, -1, 2, 4

然后，例如对于 i=1，3 个绝对成对和是

  4 1 1

他们的中位数是 1。

然后，例如对于 i=2，3 个绝对成对和是

  4 1 3

他们的中位数是 3。

这是一个更长的例子，有正面和负面的 y[] :

 -1.27 -0.69 -0.56 -0.45 -0.23  0.07  0.13  0.46  1.56  1.72

这是我的新 b_slow[] (这是地面实况，计算的天真方式):

1.20 0.92 1.00 1.01 0.79 0.53 0.56 0.53 1.33 1.49

但是现在，我的新 a_fast[]不再匹配:

 -1.20 -0.62 -0.49 -0.38 -0.16 -0.16 -0.10  0.23  1.33  1.49

编辑:

这是我对 Francis 解决方案的实现(直到我们有两个排序数组，其中位数很容易计算)。我在 R 中这样做是为了保持问题的精神。

尽管如此，我似乎缺少索引的校正因子(下面代码中的 ww)，所以下面的代码有时会稍微偏离一点。这是因为在上面的定义中，我们计算了 n-1 个观测值 (i!=j) 的中位数。

 n<-100
 y<-rnorm(n)
 y<-sort(y)

 b<-rep(NA,n)
 #Naive --O(n**2)-- approch:
 for(i in 1:n){
     b[i]<-median(abs(y[-i]+y[i]))
 }

 k<-rep(NA,n)
 i<-1
 k[i]<-min(na.omit(c(which(y+y[i]>0)[1],n))) #binary search: O(log(n)) -- 
 for(i in 2:n){                  #O(n)
     k_prov<-k[i-1]
     while(y[k_prov]+y[i]>0 && k_prov>0)     k_prov<-k_prov-1
     k[i]<-max(k_prov+1,1)
     #for(i in 1:n){ should give the same result.
     #   k[i]<-which(y+y[i]>0)[1]
     #}
 }

 i<-sample(1:n,1)
 x1<--y[1:(k[i]-1)]-y[i]
 x2<-y[i]+y[n:k[i]]
 x3<-c(x1,x2)
 plot(x3)
 ww<-ifelse(i<k[i] & i>n/2,n/2+1,n/2)
 sort(x3)[ww]  #this can be computed efficiently: O(log(n))
 b[i]          #this is the O(n**2) result.

Answer 1

这是一个 O(Nxln(N)xln(N)) 的解决方案:

对于所有的我:

1) 找到第k项，例如j<k <=> y[j]+y[i]<0 (二分法，O(ln(N)))

k 分隔两个排序列表:一个在 -y[i] 之上，另一个在 -y[i] 之下，应更改其符号以获得 abs(y[i]+y[j])。 现在，我们正在寻找这些列表的中位数。

从这里看，就是finding the median of two sorted lists的问题了, 重复 n 次。

2)让我们选择这些列表中的最大值 (M=abs(y[1]-y[i]) 或 M=abs(y[size]-y[i])) 和最小值 (m around k)并重新开始二分法 (O(ln(N))。让我们从选择中间 (M+m)/2...开始...在任何阶段，让我们选择中间...

3)这个大二分法的阶段:第一个列表中有多少项 y[j]+y[i] 在 (M+m)/2 以上？再次二分法... O(ln(N))。在第二个列表中，有多少项 -y[j]-y[i] 在 (M+m)/2 以上？你猜怎么着 ？二分法...将这两个数字相加。如果大于(size-1)/2，则m=(M+m)/2。否则M=(M+m)/2。

4)如果m=M停止! b[i]=m;

我猜有人会提出更好的解决方案...

编辑:我应该感谢 @user189035 链接到 O(ln(n+m)) 算法来计算两个排序列表的中值。 How to find the kth smallest element in the union of two sorted arrays?

再见，