更新：问题的症结在于，为了达到的时间复杂度，需要的存储量。$O(n\log(n))$$O(n)$

不，是（见（1））元素的时间复杂度的理论下限可能的。$O(n\log(n))$$k^{th}$$\frac{n(n-1)}{2}$$|x_i - x_j|: 1 \leq i \lt j \leq n$

您可以获得空间，但只能通过在时间中天真地检查的所有组合。$O(1)$$x_i-x_j$$O(n^2)$

好消息是您可以使用在package的函数中规模估计器（参见 (2) 和 (3) 的改进版本和一些时序比较） 。单变量估计器是一个两步（即重新加权）尺度估计器。它具有 95% 的高斯效率、50% 的故障点以及时间和空间的复杂性（此外，它可以很容易地“在线”，在重复使用中减少一半的计算成本——尽管你将不得不深入研究代码来实现这个选项，这很简单）。$\tau$scaleTau2()Rrobustbase$\tau$$O(n)$$O(1)$R

1. X + Y 中选择和排序的复杂性以及具有排序列的矩阵 GN Frederickson 和 DB Johnson，计算机和系统科学杂志第 24 卷，第 2 期，1982 年 4 月，第 197-208 页。
2. Yohai, V. 和 Zamar, R. (1988)。通过最小化有效尺度的回归的高分解点估计。美国统计协会杂志 83 406–413。
3. Maronna, R. 和 Zamar, R. (2002)。高维数据集的位置和分散的稳健估计。技术计量学 44 307–317

编辑使用这个

1. 启动R（它是免费的，可以从这里下载）
2. 通过键入以下命令安装包：

install.packages("robustbase")

3. 通过键入以下内容加载包：

library("robustbase")

4. 加载数据文件并运行函数：

mydatavector <- read.table("address to my file in text format", header=T)
scaleTau2(mydatavector)

（非常简短的回答）评论文字说

避免在评论中回答问题。

所以这里是这样：有一篇关于在线算法的论文似乎运行得很好： Applying the Estimator Online$Q_n$。

编辑

（由用户 user603）。本文中链接的算法是的移动窗口版本。$Q_n$

给定一个大样本分为宽度为的时间窗口，我们可以将应用于每个时间窗口产生值。表示这些值$\{x_i\}_{i=1}^N$$n<N$$\{x_i\}_{i=t-n+1}^t$$Q_n$$N-n+1$$Q_n$$\{Q_n^i\}_{i=1}^{N-n+1}$

这里引用的算法允许以低于从头计算所需的最坏情况的平均$Q_n^i|Q_n^{i-1}$ $O(n\log(n))$$Q_n^i$

然而，该算法不能用于计算完整原始样本。它还需要维护一个缓冲区，其大小可以与一样大（尽管它通常要小得多）。$Q_n$$\{x_i\}_{i=1}^N$$O(n^2)$

这是我的 Qn 实现...

我在 C 中编程，结果是这样的：

void bubbleSort(double *datos, int N)
{
 for (int j=0; j<N-1 ;j++)     
  for (int i=j+1; i<N; i++)    
   if (datos[i]<datos[j])      
   {
    double tmp=datos[i];
    datos[i]=datos[j];
    datos[j]=tmp;
   }
}

double  fFactorial(long N)    
{
 double factorial=1.0;

 for (long i=1; i<=N; ++i)
  factorial*=(double)i;

 return factorial;  
}

double fQ_n(double *datos, int N)  // Rousseeuw's and Croux (1993) Qn scale estimator
{
 bubbleSort(datos, N);

 int m=(int)((fFactorial((long)N))/(fFactorial(2)*fFactorial((long)N-2)));

 double D[m];
 //double Cn=2.2219;      //not used now :) constant value https://www.itl.nist.gov/div898/software/dataplot/refman2/auxillar/qn_scale.htm

 int k=(int)((fFactorial((long)N/2+1))/(fFactorial(2)*fFactorial((long)N/2+1-2)));

 int y=0;

 for (int i=0; i<N; i++)
  for (int j=N-1; j>=0; j--)
   if (i<j)
   {
    D[y]=abs(datos[i]-datos[j]);
    y++;
   }

 bubbleSort(D, m);

 return D[k-1];
}

int main(int argc, char **argv)    
{
 double datos[6]={1,2,3,5,6,7};
 int N=6;

 // Priting in terminal the final solution
 printf("\n==[Results] ========================================\n\n");

 printf(" Q_n=%0.3f\n",fQ_n(datos,N));

 return 0;
}