Biarkan $Q_n = C_n.\{|X_i-X_j|;i < j\}_{(k)}$ jadi untuk sampel yang sangat singkat seperti $\{1,3,6,2,7,5\}$ dapat dihitung dari menemukan urutan $k$ statis dari perbedaan berpasangan:

    7 6 5 3 2 1
1   6 5 4 2 1
2   5 4 3 1
3   4 3 2
5   2 1
6   1
7

h = [n / 2] + 1 = 4

k = h (h-1) / 2 = 8

Jadi $Q_n=C_n. 2$

Jelas untuk sampel besar mengatakan terdiri dari 80.000 catatan, kami membutuhkan memori yang sangat besar.

Apakah ada pula untuk menghitung dalam ruang 1D bukan 2D?$Q_n$

Tautan ke jawaban ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf meskipun saya tidak dapat memahaminya sepenuhnya.

Pembaruan: Inti masalahnya adalah bahwa untuk mencapai kompleksitas waktu $O(n\log(n))$ , seseorang perlu dalam urutan penyimpanan $O(n)$ .

Tidak, $O(n\log(n))$ adalah teori batas bawah untuk kompleksitas waktu (lihat (1)) memilih $k^{th}$ elemen antara semua $\frac{n(n-1)}{2}$ mungkin$|x_i - x_j|: 1 \leq i \lt j \leq n$.

Anda bisa mendapatkan ruang $O(1)$ , tetapi hanya dengan secara naif memeriksa semua kombinasi $x_i-x_j$ dalam waktu $O(n^2)$ .

Berita baiknya adalah Anda dapat menggunakan penaksir skala $\tau$ (lihat (2) dan (3) untuk versi yang ditingkatkan dan beberapa perbandingan waktu), yang diimplementasikan dalam fungsi scaleTau2()dalam Rpaket robustbase. Estimator $\tau$ univariat adalah penduga skala dua langkah (yaitu re-weighted). Ini memiliki efisiensi Gaussian 95 persen, titik rincian 50 persen, dan kompleksitas $O(n)$ waktu dan $O(1)$ ruang (ditambah dapat dengan mudah dibuat 'online', mengurangi setengah dari biaya komputasi dalam penggunaan berulang - meskipun Anda harus menggali ke dalam Rkode untuk mengimplementasikan opsi ini, ini agak mudah dilakukan).

1. Kompleksitas seleksi dan peringkat dalam X + Y dan matriks dengan kolom diurutkan GN Frederickson dan DB Johnson, Jurnal Ilmu Komputer dan Sistem Volume 24, Edisi 2, April 1982, Halaman 197-208.
2. Yohai, V. dan Zamar, R. (1988). Perkiraan titik breakdown yang tinggi dari regresi dengan meminimalkan skala yang efisien. Jurnal Asosiasi Statistik Amerika 83 406-413.
3. Maronna, R. dan Zamar, R. (2002). Perkiraan lokasi dan dispersi yang kuat untuk set data dimensi tinggi. Technometrics 44 307-317

Edit Untuk menggunakan ini

1. Nyalakan R(gratis dan dapat diunduh dari sini )
2. Instal paket dengan mengetik:

install.packages("robustbase")

3. Muat paket dengan mengetik:

library("robustbase")

4. Muat file data Anda dan jalankan fungsinya:

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

(Jawaban sangat singkat) Teks untuk berkomentar mengatakan

hindari menjawab pertanyaan dalam komentar.

$Q_n$

EDIT

$Q_n$

Given a large sample $\{x_i\}_{i=1}^N$ divided into time windows of width $n<N$, $\{x_i\}_{i=t-n+1}^t$ we can apply the $Q_n$ to each time window yielding $N-n+1$ values of the $Q_n$. Denote these values $\{Q_n^i\}_{i=1}^{N-n+1}$

The algorithm cited here allows to obtain $Q_n^i|Q_n^{i-1}$ at an average cost less than the worst case $O(n\log(n))$ needed to compute $Q_n^i$ from scratch.

This algorithm can however not be used to compute the $Q_n$ of the full original sample $\{x_i\}_{i=1}^N$. It also needs to maintain an buffer whose size can be as large as $O(n^2)$ (though it is often much smaller).

this is my implement of Qn...

I was programming this in C and the result is this:

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;
}