用于计算排序数组的pariwise绝对和的中值的高效算法

Question

我试图想出一个快速算法计算量b[i]= med |y_i+y_j|, 1<=j!=i<=n时,y_1,...,y_n已经排序(所以b[]是相同长度的向量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的向量

-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

编辑:

这是我对弗朗西斯解决方案的实现(直到我们有两个排序数组,其中位数易于计算).我在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])。现在，我们正在寻找这些列表的中位数。

从这里开始，这只是找到两个重复n次的排序列表的中位数的问题。

2）让我们选择这些列表中的最大值（M=abs(y[1]-y[i]) 或 M=abs(y[size]-y[i])）和最小值（m 大约 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)) 算法来计算两个排序列表的中位数。如何在两个已排序数组的并集中找到第 k 个最小元素？

再见，