我试图想出一个快速算法计算量b[i]= med |y_i+y_j|, 1<=j!=i<=n时，y_1,...,y_n已经排序（所以b[]是相同长度的向量y[]）。我将假设的所有元素y[]都是唯一的，并且n是偶数。

因此，下面的代码计算的b[i]naive（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.